[백준/Python] 2178. 미로 탐색

📄 문제

백준
난이도 : Silver 1
문제 제목 : 미로 탐색

✏️ 풀이 1

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(input().strip()) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]
result = n * m

dy = (-1, 0, 0, 1)
dx = (0, -1, 1, 0)
def bfs(start_row, start_col):
    deq = deque([[start_row, start_col]])
    dist[start_row][start_col] = 1
    
    while deq:
        y, x = deq.popleft()
        current_dist = dist[y][x]
        if x == m - 1 and y == n - 1:
            result = current_dist
            print(result)
            break
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or nx < 0 or ny >= n or nx >= m:
                continue
            if dist[ny][nx] != -1 or graph[ny][nx] == '0':
                continue
            deq.append([ny, nx])
            dist[ny][nx] = current_dist + 1

bfs(0, 0)

BFS의 기본적인 응용 문제로, 거리 측정 문제이다.

이러한 문제는 현재 방문 중인 곳의 값을 기준으로 deque 에 새롭게 넣을 상하좌우 칸의 값으로 +1 한 값을 배열에 저장해주면 된다.

이 때 visited 배열 대신 각 위치를 -1 로 초기화한 dist 배열을 두고, 해당 배열(dist)에 거리 값을 저장하는 방식으로 하면 메모리를 절약할 수 있다.

이 문제에서는 시작점과 도착점 모두 칸을 세주어야 하므로, bfs 함수 실행 시 dist[start_row][start_col]를 1로 할당한다.

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '2178. 미로 탐색'
GitHub - [9강] BFS/연습문제 '2178. 미로 탐색'

---

BFS의 대표적인 응용 유형인 '거리 측정' 유형의 가장 기본적인 문제라 정리를 해보았다.