백준 2178 미로 탐색

문제

미로 탐색

미로를 탈출하는 최단 경로 계산

난이도 : Silver1

---

풀이

1. bfs로 미로 탈출 구현
2. 가능한 거리를 모두 저장하고 최솟값만 출력

---

코드

from collections import deque
import sys

N, M = tuple(map(int, sys.stdin.readline().split()))
data = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
answers = []  # 최종 거리 후보군 저장 리스트
q = deque([(0, 0, 1)])  # 시작점 (1, 1) -> index(0, 0) + 최초 거리 1
data[0][0] = 0  # 시작과 동시에 탐색

while q:
    i, j, dis = q.popleft()
    if i == N-1 and j == M-1:  # 마지막 점에 도달
        answers.append(dis)  # answers에 현재까지 거리 추가하고 반복문 계속
        continue
    
    for d in range(4):
        r = i + direction[d][0]
        c = j + direction[d][1]

        if 0 <= r < N and 0 <= c < M:
            if data[r][c] == 1:
                q.append((r, c, dis+1))  # 거리 1 추가
                data[r][c] = 0  # 방문 지점 0으로 만들어서 다시 탐색 안하도록
    
print(min(answers))