[백준] 2178 - 미로탐색 [Python(파이썬)]

문제

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

2178번: 미로 탐색

 

풀이

이 문제는 최단 거리를 구하는 문제이기 때문에 너비우선탐색을 적용해서 풀어야 하는 문제다. 문제 자체는 아주 단순하다. 너비우선탐색 시 enqueue를 할 땐 큐에 좌표와 함께 누적 거리+1(dist+1)을 삽입해주고, pop할 때는 현재 방문한 좌표를 확인해서 목적지에 도달했는지 확인한다. 만약 도달하지 않았다면 계속해서 탐색을 진행하고, 도달했다면 누적 거리(dist)를 반환하면 된다.

 

 

코드

import sys
import collections

def bfs():
    queue = collections.deque([[0, 0, 1]])
    while queue:
        y, x, dist = queue.popleft()
        if y == n-1 and x == m-1:
            return dist
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if g[ny][nx] and not visited[ny][nx]:
                    visited[ny][nx] = 1
                    queue.append([ny, nx, dist+1])

n, m = map(int, sys.stdin.readline().split())
g = [[int(x) for x in sys.stdin.readline().strip()] for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

print(bfs())