[bfs/백준] 1525번 : 퍼즐

- 문제 : https://www.acmicpc.net/problem/1525

 

문제 이해 

- 3 x 3 행렬에서 0인 지점을 기준으로 bfs를 하는 문제다. 

 

- 0이 상하좌우 움직이면서 i행 j열의 값이 (3 * i + j) 값이 아닌 경우 0과 swap한다. 

 

- 0이 오른쪽 아래까지 갈 수 있는 최단 경로를 출력하는 문제다. 

 

- 처음에는 (행, 열) : 숫자 형식으로 딕셔너리를 만들었는데, 이렇게 하니 17%에서 계속 틀렸다. 이유로는 0이 상하좌우로 움직일 때마다 전체 행렬의 모습이 조금씩 달라지는데 그걸 공통 visit로 처리를 해서 각 케이스를 모두 담아내지 못해서 그런 것 같다. 

 

- 그래서 풀이를 찾아보니 전체 퍼즐 모양을 문자열로('123456780') 처리한 뒤, 그 문자열이 되기까지의 최단 경로를 딕셔너리에 저장하면 되었다. {퍼즐 모양(문자열) : 연산횟수} 형식이다.

 

- visit만 약간 형식이 다르고, 나머지는 일반 bfs로 풀면 된다.

 

풀이 로직

- 초기값을 입력받고 puzzle에 문자열로 저장한다.

- visit는 {'퍼즐순서' : 연산횟수}를 원소로 가지는 딕셔너리다.

- queue와 while문을 가지고 bfs를 진행하고, answer에 정답을 저장한다.

- 도착한 puzzle의 모양이 정답인 '123456780'인 경우 answer를 입력한다.

- 아직 정답에 도착하지 않았다면 문자열에서 0의 행, 열의 위치(x, y)를 찾은 다음, 이동 횟수(count)를 +1 한다.

-  상하좌우로 이동한 nx, ny의 값은 행렬의 값이므로, 이를 문자열에서의 인덱스 값으로 바꿔준다. nz = 3 * nx + y

- puzzle을 리스트로 바꾼 뒤, 문자열에서 nz의 값(0에서 상하좌우로 이동한 값)과 z의 값(0)을 바꾼다.

- 새로 바꾼 new_puzzle을 이전에 방문한 적이 없다면 딕셔너리 visit를 count로 갱신한 뒤 queue로 이동하면 된다.

 

정답 풀이 

from collections import deque

puzzle = ""
for i in range(3):
    puzzle += ''.join(list(input().split()))
    
visit = {puzzle : 0}
queue = deque()
queue.append(puzzle)
answer = -1
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

while queue:
    puzzle = queue.popleft()
    count = visit[puzzle]
    z = puzzle.index('0')
    
    if puzzle == '123456780':
        answer = count
        
    x, y = z // 3, z % 3   
    count += 1
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < 3 and 0 <= ny < 3:
            nz = nx * 3 + ny
            puzzle_list = list(puzzle)
            puzzle_list[z], puzzle_list[nz] = puzzle_list[nz], puzzle_list[z]
            new_puzzle = ''.join(puzzle_list)
            
            if new_puzzle not in visit.keys():
                visit[new_puzzle] = count
                queue.append(new_puzzle)
                
print(answer)

 

참고한 블로그 : [백준] 1525번 : 퍼즐