[알고리즘] 미로의 최단거리 통로(BFS 활용)

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

---

7 * 7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요.

경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다.

출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다.

격자판의 1은 벽이고, 0은 도로이다.

격자판의 움직임은 상하좌우로만 움직인다.

미로가 다음과 같다면

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

입력설명

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

출력설명

첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -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	12
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 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 0	12
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0	14
0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0	-1
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0	18
0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0	-1

---

해결방법

1. 상, 하, 좌, 우를 나타내는 x좌표와 y좌표를 가지는 리스트를 생성
2. 미로에서 들린 좌표를 저장하는 리스트 생성.
3. BFS를 이용하여 앞으로 한칸씩 전진한다.
4. 가장 빨리 도착했을 경우 해당 L를 출력한다.

   동작 시각화

---

코드

from collections import deque

# 상, 우, 하, 좌
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

# 미로 생성
miro = [list(map(int, input().split())) for _ in range(7)]

# 미로 체크
ch_miro = [[0] * 7 for _ in range(7)]

# 첫 Root 노드 넣기
dQ = deque()
dQ.append((0, 0))

ch_miro[0][0] = 1

L = 0
# 도착했는지 확인
arrived = False

while True:
    # 몇번 움직였는지 알기 위해서
    size = len(dQ)
    
    # 길이 없을 경우
    if size == 0:
        print(-1)
        break

    for _ in range(size):
        now = dQ.popleft()

        if now == (6, 6):
            arrived = True
            print(L)
            break

        for i in range(4):
            if 0 <= now[0] + dx[i] < 7 and 0 <= now[1] + dy[i] < 7:
                if miro[now[0] + dx[i]][now[1] + dy[i]] == 0:
                    if ch_miro[now[0] + dx[i]][now[1] + dy[i]] == 0:
                        dQ.append((now[0] + dx[i], now[1] + dy[i]))
                        # print((now[0] + dx[i], now[1] + dy[i]))
                        
                        # 돌았으니 1 대입
                        ch_miro[now[0] + dx[i]][now[1] + dy[i]] = 1
        
    if arrived:
        break
    else:
        L = L + 1