백준 문제 풀이 - 퍼즐 1525번

📜 문제 이해하기

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.
1 2 3
4 5 6
7 8 0
어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.
1 0 3
4 2 5
7 8 6
--------->
1 2 3
4 0 5
7 8 6
--------->
1 2 3
4 5 0
7 8 6
--------->
1 2 3
4 5 6
7 8 0
가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

💡 문제 재정의

8퍼즐 문제를 풀어보자.

✏️ 계획 수립

위 행렬을 string형태로 저장하고 BFS로 모든 경우의 수를 찾아보고 값이 존재한다면 출력하면 된다.

💻 계획 수행

import sys
from collections import deque

# 상, 하, 좌, 우
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs():

    while q:
        now = q.popleft()

        # 만족하는 퍼즐일 경우 이동횟수 리턴
        if now == "123456789":
            return cntDict[now]

        # 현재 빈칸 위치 (행, 열) 
        pos = now.find("9")
        x = pos // 3
        y = pos % 3

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 3 and 0 <= ny < 3:
                # 이동할 위치
                nPos = nx * 3 + ny
                # 이동된 상태 설정
                nextNum = list(now)
                nextNum[nPos], nextNum[pos] = nextNum[pos], nextNum[nPos]
                nextNum = "".join(nextNum)

                if not cntDict.get(nextNum):
                    # 이동된 상태 저장, 이동횟수 + 1
                    q.append(nextNum)
                    cntDict[nextNum] = cntDict[now] + 1


# 초기 퍼즐 상태
start = ""
for _ in range(3):
    # 입력 -> 123456780 형태로 변환
    temp = sys.stdin.readline().strip()
    temp = temp.replace(" ", "")
    start += temp

start = start.replace("0", "9")

# 이동된 상태 저장
q = deque()
q.append(start)

# 이동된 상태, 이동횟수 저장
cntDict = dict()
cntDict[start] = 0

# 이동이 불가하면 "-1"을 출력
result = bfs()
print(result if result != None else "-1" )

🤔 회고

처음에는 a* 알고리즘으로 휴리스틱하게 풀어보려했는데 잘 되지 않았다. 결국 bfs로 모든 경우의 수를 찾는게 가장 쉬운 방법이었다.