[BOJ]2178 - 미로 탐색 (Python)

문제 

https://www.acmicpc.net/problem/2178

코드 

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()


def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = 1
    while queue:
        cx, cy = queue.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = cx + dx, cy + dy
            if 0 > nx or nx > N-1 or ny < 0 or ny > M-1:
                continue
            if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                graph[nx][ny] = graph[cx][cy] + 1
                visited[nx][ny] = 1
                queue.append((nx, ny))
    return graph[N-1][M-1]


N, M = map(int, input().split())
graph = [[0] * M for _ in range(N)]
visited = [[0] * M for _ in range(N)]
for i in range(N):
    graph[i] = list(map(int, input()))

print(bfs(0, 0))

 

풀이 

그동안 풀었던 DFS/BFS 문제와 비슷하지만 탐색하는 node의 개수를 세는 부분이 추가되었다고 생각하며 풀었다 

그래서 이미 지나온 길의 node에 그 길까지 가는데 지난 node의 개수를 더해주었다 

이렇게 푸니까 금방 풀 수 있었다!!