[Python] [백준 / BOJ] 2178번 : 미로 탐색

📌 문제 링크

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

---

📌 문제 풀이

from collections import deque

n, m = map(int, input().split())
lst = [list(map(int, input())) for _ in range(n)]

# 상, 하, 좌, 우 이동
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(x, y):
    q = deque()
    q.append((x, y))                            # 시작 좌표 큐에 삽입

    while q:
        x, y = q.popleft()                      # 현재 위치 꺼냄

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 내이고 이동 가능한 길(1)인 경우
            if nx >= 0 and nx < n and ny >= 0 and ny < m and lst[nx][ny] == 1:
                q.append((nx, ny))
                lst[nx][ny] = lst[x][y] + 1     # 이전 칸 거리 + 1로 최단거리 갱신

    return lst[n-1][m-1]                        # 도착 지점까지의 최단 거리 반환

print(bfs(0, 0))                                # (0,0)에서 시작

1. 해당 문제는 미로에서 출발 지점부터 도착 지점까지의 최단 거리를 구해야 하므로 BFS를 이용해 접근
2. 먼저 미로의 크기 n, m과 각 칸의 정보를 입력받아 2차원 리스트 lst에 저장하고, 상하좌우 이동을 위한 방향 벡터 dx, dy를 설정
3. BFS 함수에서는 시작 좌표 (0, 0)을 큐에 넣고, 큐에서 좌표를 하나씩 꺼내며 상하좌우로 이동 가능한 칸을 탐색
4. 이동 가능한 칸은 값이 1인 경우이며, 해당 칸에 도달했을 때 이전 칸의 값에 1을 더해 최단 거리 정보를 함께 저장
5. BFS 특성상 먼저 방문하는 경로가 항상 최단 경로이므로, 한 번 값이 갱신된 칸은 다시 방문하지 않아도 됨
6. 탐색이 종료되면 도착 지점 (n-1, m-1)에 저장된 값이 곧 출발 지점부터의 최단 거리이므로 이를 반환하여 출력