백준_python 2178번 미로 탐색(그래프, BFS)

<문제 링크>

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

2178번: 미로 탐색

 

 

<정답 코드>

from collections import deque
 
n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]
 
 
def bfs(graph, x, y):
    q = deque([(0, 0)])
    
    # 상하좌우 이동 값
    dx = [-1, 1, 0, 0]        
    dy = [0, 0, -1, 1]
 
 
    while q:
        x, y = q.popleft()
 
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                q.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
 
    return graph[n-1][m-1]
 
print(bfs(maze, 0, 0))

 

현재 위치에서 상하좌우 중 움직일 수 있는 방향의 값에 +1을 해서

특정 위치에 도달하려면 몇번 이동해야하는지를 구한다

 

 

마지막 graph 상태