[BOJ][Python] 백준 1525번: 퍼즐

1일 1PS 62일차!

📚 문제

---

골드 2 퍼즐

💡 풀이 과정

---

• 3*3 사이즈이므로 충분히 모든 경우의 수에 대해 조사 가능하다.
• BFS 를 통해 진행하면 visited 에 저장되는 이동 횟수들은 모두 최소이므로 따로 최신화가 필요없다.

📌포인트

---

• 처음에는 딕셔너리에 board 자체를 넣으려했지만 Key 값에는 리스트 형태가 들어가지 못한다.
• 리스트를 변환시켜야 했는데 str(board) 를 다시 리스트로 만드는 과정보다는 모든 요소가 한자리수이므로 직관적으로 공백없이 모든 요소를 문자열로 저장하는 형태로 변환하였다.

💻 코드

---

import copy
from collections import deque

input_board = [list(input().split()) for _ in range(3)]
board = ''.join(''.join(b) for b in input_board)

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {''.join(board): 0}
answer = '123456780'

queue = deque()

queue.append(board)


def bfs():
    while queue:
        b = queue.popleft()
        cnt = visited[b]

        if b == answer:
            return cnt

        zero = b.index('0')
        x_zero, y_zero = zero // 3, zero % 3

        for i in range(4):
            nx, ny = x_zero + dx[i], y_zero + dy[i]

            if 0 <= nx <= 2 and 0 <= ny <= 2:
                nz = nx * 3 + ny
                b_list = list(b)
                b_list[zero], b_list[nz] = b_list[nz], b_list[zero]
                temp = ''.join(b_list)

                if temp not in visited:
                    visited[temp] = cnt + 1
                    queue.append(temp)

    return -1


print(bfs())