[백준 1525] 퍼즐

출처: https://sarangsai.com/102

1525번: 퍼즐

문제

위와 같은 3x3 퍼즐이 있을 때 퍼즐위의 숫자들을 오름차순으로 정렬할 수 있는 최소 이동 횟수를 구하는 문제입니다. 얼핏보면 그냥 평범한 백트래킹 혹은 BFS 문제처럼 보이지만 메모리 제한(25MB)이 걸려있습니다.

접근

일반적인 BFS를 이용한 최소 비용을 구하는 문제들은 visited라는 방분 여부 변수를 사용하는데 이 문제에서는 visitied 배열을 9차원 배열로 선언해야 합니다. (ex: visited[0][1][2][3][4][5][6][7][8]) 그렇게 되면 visited의 크기는 9^9가 되는데 이 길이는 억단위를 넘어가기 때문에 메모리 제한에 걸리게 됩니다. 그리고 이 문제에서의 퍼즐은 1~8,0 숫자가 반드시 중복되지 않고 한 번 씩만 나오기 때문에 상당히 비효율적인 구조 입니다. 즉, 이 문제는 방문 여부를 저장하는 방법을 찾아야 합니다.

풀이 (파이썬 기준)

3x3배열을 문자열로 바꾸고 이 문자열을 key로 하는 딕셔너리(혹은 해시맵)을 선언하면 됩니다.

1 2 3
4 5 6
7 8 0
을
123456780

딕셔너리를 선언하고 문자열을 key로 저장하게 되면, 방문한 퍼즐 구조만 visited에 저장하기 때문에 메모리를 절약할 수 있습니다.

결국 3x3형태의 2차원 배열을 문자열로 바꾼 다음 BFS를 진행하면 풀리는 문제 입니다.

코드 보기

import sys
import collections
import heapq
input = sys.stdin.readline

visited = collections.defaultdict(int)

def swap_chars(s, i, j):
    # i위치와 j위치의 문자 swap하기
    x, y = s[i], s[j]
    return s[:i] + y + s[i+1:j] + x + s[j+1:]

a = ''
for _ in range(3):
    _raw = ''.join(input()[:-1].split())
    a += _raw

q = [(0, a)]


while q:
    cnt, s = heapq.heappop(q)
    if s == '123456780':
        break
    else:
        p = 0
        for p in range(0, 10):
            if s[p] == '0':
                break
        # 위
        if p >= 3:
            next_s = swap_chars(s, p-3, p)
            if visited[next_s] == 0 or visited[next_s] > cnt + 1:
                visited[next_s] =  cnt + 1
                heapq.heappush(q, (cnt + 1, next_s))
        # 아래
        if p < 6:
            next_s = swap_chars(s, p, p+3)
            if visited[next_s] == 0 or visited[next_s] > cnt + 1:
                visited[next_s] =  cnt + 1
                heapq.heappush(q, (cnt + 1, next_s))
        # 왼쪽
        if p % 3 > 0:
            next_s = swap_chars(s, p-1, p)
            if visited[next_s] == 0 or visited[next_s] > cnt + 1:
                visited[next_s] =  cnt + 1
                heapq.heappush(q, (cnt + 1, next_s))
        # 오른쪽
        if p % 3 < 2:
            next_s = swap_chars(s, p, p+1)
            if visited[next_s] == 0 or visited[next_s] > cnt + 1:
                visited[next_s] =  cnt + 1
                heapq.heappush(q, (cnt + 1, next_s))

if visited['123456780'] > 0 or a == '123456780':
    print(visited['123456780'])
else:
    print(-1)

일단 이 포스트에 올린 코드는 1128ms에 작동되는 코드가 맞고 아래는 코드 길이를 줄이기 위해 큐에 들어갈 요소를 문자열이 아닌 3x3으로 바꿔서 구현한 코드 입니다. 얕은 복사(copy())의 비용이 큰 나머지 시간이 오래 걸린 것 같군요.