미로의 최단거리 통로(BFS 활용)

7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는
출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.
격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위와 같은 경로가 최단 경로이며 경로수는 12이다.

▣ 입력설명

7*7 격자판의 정보가 주어집니다.

▣ 출력설명

첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

▣ 입력예제 1

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0
▣ 출력예제 1
12

풀이

• 이 경우 BFS를 활용하면 되는데 각각의 시작점부터 거리를 기록해놓는 2차원 리스트가 중요합니다. -> dis 2차원리스트
• 또한, 이 경우에 왔던길을 되돌아가지 않아야 하므로 그에 대한 처리를 하지 않으면 무한 루프에 빠질 수 있습니다.

from collections import deque


dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

n = 7
board = [list(map(int, input().split())) for _ in range(n)]
board[0][0] = 1
dis = [[0] * n for _ in range(n)]
deq = deque([(0, 0)])
while deq:
    x, y = deq.popleft()
    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]
        if 0 <= new_x < n and 0 <= new_y < n and board[new_y][new_x] == 0:
            board[new_y][new_x] = 1 # 1
            deq.append((new_x, new_y))
            dis[new_y][new_x] = dis[y][x] + 1 # 2

for i in dis:
    print(i)
if dis[6][6] == 0:
    print(-1)
else:
    print(dis[6][6])

• 여기서 1번의 board[new_y][new_y] = 1은 왔던 길을 되돌아가지 않도록 하는 처리입니다.
• 2번은 이제 거리를 기록해 놓는 코드입니다. 이렇게 해서 모든 좌표의 거리는 dis 2차원 리스트에 담기게 됩니다.
• 도착점은 (6, 6) 고정이므로 출력은 dis[6][6]으로 출력하였고, 도착점에 갈 수 없을 때에는 dis[6][6] == 0이므로 -1을 출력하게 만들었습니다.

회고

• 사실 이 문제를 바로 풀지 못했습니다.
• 이 문제를 풀 때 문제였던 점은

1. 왔던 길을 되돌아가지 않게 하려면 어떻게 할까?
2. 어떻게 하면 최소 거리를 찾을 수 있을까?

• 이 두 가지 문제점을 제대로 해결하지 못했습니다. 하지만 지금 풀이를 보면

1. board에 1로 마킹
2. 모든 거리를 dis 2차원 리스트에 저장

• 이 두 가지 방식으로 해결할 수 있었습니다.
  앞으로도 이렇게 어떤 것이 문제였는지 한 번 더 상기시켜보고 명확한 해결책을 글로 써볼 예정입니다.