백준 2178번 Python / BFS

너비 우선 탐색(BFS)이란?

https://seokii.tistory.com/31

[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)이란?

너비 우선 탐색 알고리즘 개념에 대한 내용입니다.

 

문제링크

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

2178번: 미로 탐색

 

풀이

from collections import deque

n, m = map(int, input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int, input())))

def bfs(x,y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            
            if graph[nx][ny] == 0:
                continue
            
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n-1][m-1]

print(bfs(0,0))