BOJ 2178: 미로 탐색 (Python)

문제

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

2178번: 미로 탐색

 

 

코드

import sys
from collections import deque

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<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]

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]

print(bfs(0,0))

 

풀이

bfs를 이용해 문제를 풀었다. (0,0) 위치부터 탐색을 시작하여 상하좌우에 있는 값이 1이라면, 즉 아직 지나가지 않았고 지나갈 수 있는 길이라면 그 값에 이때까지 온 경로의 + 1 을 한 값을 넣는다. 그리고 그것의 좌표 값을 큐에 담는다.

큐에 남는게 없을 때까지 반복하고 나면 graph[n-1][m-1] ( (0,0)부터 시작했으므로 오른쪽 가장 아래의 좌표는 (n-1, m-1)이다. )에 들어가 있는 값이 최소 경로 값으로 정답이다.