[백준/BOJ] gold2 - 1525번 퍼즐 (Python)

▶1525 - 퍼즐

백준 로고

▶문제

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

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

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

 

▶입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈칸은 0으로 나타낸다.

 

▶출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

728x90

▶풀이

입력된 3x3배열을 한 줄의 문자열로 바꿔준다.

그 문자열이 123456780이 되면 cnt를 return 해주면 된다.

 

나머지는 0의 위치를 찾아서 이를 x, y로 바꿔준다.

그다음, 0의 위치의 이웃한 자리와 위치를 바꿔주고 queue에 넣어주면 된다.

from collections import deque


def bfs():
    queue = deque()
    queue.append((puzzle, 0))

    visit = {}
    visit[puzzle] = 0

    while queue:
        now, cnt = queue.popleft()

        if now == '123456780':
            return cnt
        
        p = now.find('0')
        x = p // 3
        y = p % 3

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

            if 0 <= nx < 3 and 0 <= ny < 3:
                np = nx * 3 + ny
                nn = list(now)
                nn[np], nn[p] = nn[p], nn[np]
                nn = ''.join(nn)

                if nn not in visit:
                    queue.append((nn, cnt + 1))
                    visit[nn] = 0
    return -1


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
puzzle = ''
for _ in range(3):
    tmp = input().strip()
    tmp = tmp.replace(' ', '')
    puzzle += tmp

print(bfs())