[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())
댓글남기기