[백준 1525 🥇] 퍼즐

문제

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

1	2	3
4	5	6
7	8

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

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

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

입력

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

출력

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

문제 풀이

import sys
from collections import deque

target=[['1','2','3'],['4','5','6'],['7','8','0']]
numbers=[list(sys.stdin.readline().strip().split(' ')) for _ in range(3)]

ans=1e9

# DFS는 모든 경로를 탐색해야 해서 최단 경로를 보장하는 BFS로 풀어야 함.
# def dfs(blank,count):
#     global ans, numbers
#     if numbers==target:
#         ans=min(ans, count)
#         return
#     for di in directions:
#         by=blank[0]+di[0]
#         bx=blank[1]+di[1]
#         if 0<=by<3 and 0<=bx<3:
#             numbers[blank[0]][blank[1]]=numbers[by][bx]
#             numbers[by][bx]=0
#             dfs((by,bx),count+1)
#             numbers[by][bx]=numbers[blank[0]][blank[1]]
#             numbers[blank[0]][blank[1]]=0

visited=set()
def bfs(blank, count, numbers):
    global ans
    queue=deque()
    queue.append((blank[0], blank[1], count, numbers))
    directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    while queue:
        blank_y,blank_x,c,num=queue.popleft()
        if num==target:
            ans=c
            return
        for di in directions:
            by=blank_y+di[0]
            bx=blank_x+di[1]
            if 0<=by<3 and 0<=bx<3:
                new_numbers = [arr[:] for arr in num]
                new_numbers[blank_y][blank_x] = new_numbers[by][bx]
                new_numbers[by][bx]='0'
                str_new_number=''.join(sum(new_numbers,[]))
                if str_new_number not in visited:
                    queue.append((by,bx,c+1, new_numbers))
                    visited.add(str_new_number)

for i in range(3):
    for j in range(3):
        if numbers[i][j]=='0':
            visited.add(''.join(sum(numbers,[])))
            bfs((i,j),0, numbers)
            if ans!=1e9:
                print(ans)
            else:
                print(-1)
            sys.exit(0)

• 처음엔 DFS를 이용해서 움직이는 좌표별로 visited 배열을 매 큐마다 넣어줄 필요없이 visited를 방문 처리해줬다가 방문 처리를 해제해줬다가 하면서 DFS 탐색을 이용해서 구할 수 있을 것이라 생각해서 DFS로 풀었더니 시간 초과가 발생했다.
• numbers 배열과 target 배열이 일치하더라도 최소가 보장되지 않는 DFS 특성상 모든 경우의 수를 탐색하고 그 중 가장 작은 count 값을 구해야하기 때문에 이 문제에서 DFS를 사용하기엔 무리가 있다.
• 그래서 BFS로 변경해서 풀었다! 대신 각 경로마다 새로운 visited 배열을 큐에 넣어주면서 풀어야 한다. 배열의 크기가 크다면 메모리가 초과가 발생할 가능성이 있지만, 이 문제의 경우 3x3 배열로 고정되어 있기 때문에 가능하다. 
• 그리고 BFS를 돌면서 방문했던 표 상태인지 확인하고, 방문한 경우이면 큐에 넣어주지 않아야 한다. 이 부분에서 해당 표 상태를 지나갔었는지는 set과 문자열을 이용해서 구현했다.
• set은 in 연산자가 상수 시간이므로 visited set 안에 방문했다고 저장된 문자열인지 확인하기에 용이하다.
• numbers=[['1','0','3'],['2','5','6'],['4','7','8']]이라는 표 상태가 있다면 sum(numbers, [])를 하면 ['1','0','3','2','5','6','4','7','8']로 변경이 된다. 이렇게 변경된 배열은 ''.join(sum(numbers, []))으로 '103256478'로 변경이 되고, 이를 visited set에 넣어줘서 방문 처리를 해준다. 
• 이러한 방문 처리를 해주지 않으면 target 배열인 [[1,2,3],[4,5,6],[7,8,0]]을 구하면 return되는 BFS의 while 종료 조건을 구할 수가 없어서 무한 루프를 돌게 되므로 꼭! 방문 처리를 해줘야 한다.