[Python] 백준 #2178 미로 탐색 - bfs

문제

2178번: 미로 탐색

 

풀이

bfs의 기본이 되는 문제. 

새로 추가된 애(maze[i][j]로부터 파생된 애)의 자리에 기존(maze[i][j]) + 1을 해주는것이 가장 중요하다. 

import sys
from collections import deque

# N * M 미로 
N, M = map(int, sys.stdin.readline().split(" "))
maze = []

for _ in range(N):
    maze.append(list(map(int, sys.stdin.readline().strip())))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

# 시작점 
queue = deque()
queue.append([0, 0])

# bfs
while queue:
    i, j = queue.popleft()

    for k in range(4):
        ndr = i + dr[k]
        ndc = j + dc[k]

        if 0 <= ndr < N and 0 <= ndc < M and maze[ndr][ndc] == 1 and not (ndr == 0 and ndc == 0):
            queue.append([ndr, ndc])
            maze[ndr][ndc] = maze[i][j] + 1

            if ndr == N-1 and ndc == M-1:
                print(maze[ndr][ndc])
                break