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

백준 문제 풀이 - 그래프 탐색

📰 문제

문제 확인 🏃

💡 입출력 예제

4 6
101111
101010
101011
111011

>> 15

4 6
110110
110110
111111
111101

>> 9

2 25
1011101110111011101110111
1110111011101110111011101

>> 38

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

>> 13

💬 풀이

🎵 첫번째 풀이

from collections import deque
import sys


input = sys.stdin.readline

N, M = map(int, input().split())    
graphs = [list(map(int, input().rstrip())) for _ in range(N)]

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


def bfs():

    visited = [[False] * M for _ in range(N)]
    queue = deque()

    queue.append((0, 0, 1))
    visited[0][0] = True

    while queue:

        r, c, count = queue.popleft()

        if r == N-1 and c == M-1:
            return count

        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]

            if nr < 0 or nc < 0 or nr >= N or nc >= M or visited[nr][nc] or not graphs[nr][nc]:
                continue

            queue.append((nr, nc, count+1))
            visited[nr][nc] = True


print(bfs())

✒️ 생각