[백준] 2178 미로탐색 (BFS 풀이)

BFS로 최단거리를 구하면 되는 문제이다. 

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

2178번: 미로 탐색

부수면서 이동하기 문제의 쉬운 버전이다 ㅎㅎ 

이제 이런 간단한 그래프 문제는 한번 시도만에 바로 맞다니 ㅠㅠ 감격스러운걸...!

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    dist = [[0] * m for _ in range(n)]
    q = deque()
    q.append((0,0)) # start
    dist[0][0] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == 0 and graph[nx][ny] == 1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    return dist[n-1][m-1]

print(bfs())