[백준] 1525번 퍼즐 (by Python)

문제

https://www.acmicpc.net/problem/1525

1525번: 퍼즐

 

풀이

from collections import deque

s = ''
goal = '123456780'
for _ in range(3):
    s += ''.join(input().split())
visited = {s: True}
adj = [[1, 3], [0, 2, 4], [1, 5], [0, 4, 6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]]
ans = -1
time = 0
q = deque()
q.append((s, s.index('0')))
next_q = deque()

while q or next_q:
    if not q:
        q = next_q
        time += 1
        next_q = deque()
    now, zero = q.popleft()
    if now == goal:
        ans = time
        break
    for a in adj[zero]:
        new = list(now)
        new[zero], new[a] = new[a], new[zero]
        new = ''.join(new)
        if new not in visited:
            next_q.append((new, a))
            visited[new] = True
print(ans)

 

전체 크기가 정해져있고, 목표로 하는 모양이 있다는 점에서 조금 특이한 BFS. 이런 점들을 이용해 그때그때의 모양을 array가 아닌 string으로, visited를 dictionary로 운용할 수 있다. 원래는 가능한 모양들을 상하좌우 검사해봐야하지만, string이다보니 인덱싱이 어렵고 해서 각 인덱스별로 인접한 곳의 인덱스들을 담는 adj 리스트를 만들어 사용했다. 처음에 큐에 그때그때의 리스트를 넣어버리는 짓을 했는데, 여러 번 경험했듯 메모리 에러가 났다. 이런 해결방법은 최대한 피하는 쪽으로 할 생각이다. 또한, 이렇다보니 -1이 나오는 경우도 어떤 조건을 맞춰줘야할지 고민을 많이 했는데, visited로 인해 더 방문할 것이 없어졌다면 거기서 끝내면 된다. 생각보다 간단한 해답이 있던 문제.