[그래프 탐색] 백준 2178 미로 찾기 파이썬

문제

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

문제 요약

N X M 미로

1 이동 가능 0 이동 불가

(N,M)으로 이동하는 최단거리

문제 아이디어

출처 : https://www.youtube.com/watch?v=7C9RgOcvkvo&t=2721s&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 

 

(1, 1) 위치에서 시작한다.

 

(1, 1) 좌표에서 상하좌우 탐색을 진행하면 옆 노드인 (1,2) 위치의 노드를 방문한다.

새롭게 방문하는 (1, 2) 노드 값을 +1해준다.

 

 

BFS를 계속 수행하면 최단 경로의 값들이 1씩 증가한다.

코드

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph=[]

for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip())))

# 이동할 네 방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    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 <= -1 or nx >=n or ny <= -1 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))