meatsby.github.io

BOJ 2178 - 미로 탐색

2 min read

풀이

[0][0] 에서 [n-1][m-1] 좌표까지의 최단거리 문제이기 때문에 BFS 를 활용했다.

이제 기본적인 BFS 구조는 이해했고 다양한 방면에서 활용할 수 있다.

“아기상어” 문제에서 활용했던 dist 배열을 통해 미로를 탐색하면서 각 좌표별 시작점부터의 거리를 저장하도록 코드를 작성했다.

시작점에서 BFS 를 실행시켜 모든 탐색이 끝난 후 dist[n-1][m-1] 을 반환하여 최단거리를 계산할 수 있다.

소스코드

# 미로 탐색
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(i, j):
    q = deque()
    q.append([i, j])
    graph[i][j] = 0  # 시작 점 방문처리
    dist[i][j] = 1
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < m:  # 범위 내일 때
                if graph[nx][ny] == 1:  # 통로일 경우
                    q.append([nx, ny])
                    graph[nx][ny] = 0  # 방문 처리
                    dist[nx][ny] = dist[x][y] + 1  # 좌표별 거리 저장
    return dist[n-1][m-1]
 
 
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
 
n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
dist = [[0] * m for _ in range(n)]
 
print(bfs(0, 0))

References

Graph View