[1525] 퍼즐 - Python

/* 문제 */
3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

최소의 이동으로 퍼즐을 정리해야 한다는 점, 숫자 블록을 상하좌우로 움직일 수 있다는 점에서 그래프 문제와 비슷하다고 생각했지만 풀이법을 한 번에 떠올리기는 쉽지 않았다.

 

예전 문제에서 풀었던 대로 표를 2차원 리스트로 만들어서 구현하려고 하면 상당히 어렵다. 그렇게 할 경우 이동 횟수를 저장하기가 쉽지 않기 때문이다. 

따라서 현재 퍼즐의 상태를 문자열로 저장하고, 그 퍼즐 상태를 만들기 위해 필요한 이동 횟수를 딕셔너리로 저장한 후 bfs로 푼다.

# 정답 코드
from collections import deque

def bfs(puzzle, visited):
    queue = deque([puzzle])
    visited[puzzle] = 0
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        v = queue.popleft()
        if v == '123456780':
            return visited[v]
        pos = v.index('0')
        x0 = pos//3
        y0 = pos%3
        for i in range(4):
            x = x0 + dx[i]
            y = y0 + dy[i]
            if 0 <= x < 3 and 0 <= y <3:
                next_puzzle = list(v)
                next_puzzle[pos], next_puzzle[x*3+y] = next_puzzle[x*3+y], next_puzzle[pos]
                next_puzzle = ''.join(next_puzzle)
                if next_puzzle not in visited.keys():
                    queue.append(next_puzzle)
                    visited[''.join(next_puzzle)] = visited[v] + 1
    return -1

puzzle = ''
for _ in range(3):
    a, b, c = input().split()
    puzzle += a+b+c
visited = dict()
print(bfs(puzzle, visited))

예를 들어 입력이 '103425786'으로 들어온다면 이 문자열을 '123456780'으로 만들기 위해 bfs를 수행하고, 그 때까지의 이동 횟수를 출력해야 한다. 

bfs를 사용하는 이유는 최단거리를 구할 때와 비슷한데 현재 상태에서 움직일 수 있는 모든 경우의 수를 큐에 넣고 다음에는 확인(방문)하지 않도록 하면 항상 최소 이동 횟수를 구할 수 있기 때문이다.

 

위 코드에서 bfs 함수의 작동 과정은 다음과 같다.

• 퍼즐의 처음 상태를 큐에 넣고 탐색을 시작한다. 처음 상태의 이동 횟수는 0이다.
• 큐의 값들을 꺼내며 정렬이 완료된 상태라면 이동 횟수를 바로 반환한다.
• 현재 상태가 정렬되지 않았다면
  • 0(빈 공간)의 위치를 계산한 후
  • 상하좌우의 숫자와 swap한 결과를 구한다.
  • 다음 상태가 이전에 계산된 적이 없다면 큐에 추가한다.
• 큐가 모두 비워질 때까지 정렬이 되지 않는다면 -1을 반환한다.

---

그래프를 문자열로 바꿔서 저장하고, 방문 횟수(이동 횟수)를 딕셔너리로 저장하는 문제를 처음 풀어봤다. 이 문제가 bfs라는 것을 모르고 풀었으면 풀이법을 떠올리지 못했을 것 같다. 비슷한 문제를 찾아서 몇 번 풀어봐야겠다.