[Python] 백준 2178. 미로탐색 (BFS)

문제 링크

문제 풀이

• bfs로 탐색하되 이동한 거리를 나타내기 위해 방문한 칸의 값을 이동한 거리로 업데이트시켜준다.
• 이렇게 값이 1인 모든 칸들을 bfs로 탐색완료했을 때,
• (N, M) 위치의 칸 값을 읽으면 최소 이동 거리를 읽을 수 있도록 함

코드

import sys
from collections import deque

input = sys.stdin.readline


def bfs():
    while dq:
        r, c = dq.popleft()
        for next_r, next_c in zip((r - 1, r + 1, r, r), (c, c, c - 1, c + 1)):  # 상하좌우
            if 0 <= next_r < n and 0 <= next_c < m: #in range 체크
                if maze[next_r][next_c] == 1:    #방문하지 않았고 값이 1인 칸이면 (방문했으면 값이 1일 수가 없음)
                    maze[next_r][next_c] += maze[r][c]  #칸의 값을 이동거리로 업데이트해주고 (전 칸 이동거리 + 1)
                    dq.append([next_r, next_c]) #탐색 이어나감


if __name__ == '__main__':
    #input
    n, m = map(int, input().split())
    maze = [list(map(int, list(input().rstrip()))) for _ in range(n)]
    #탐색
    dq = deque([[0, 0]])
    bfs()
    #output
    print(maze[n - 1][m - 1])