📌 문제 요약

• 문제 이름: 2178번: 미로 탐색
• 알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색(BFS)
• 사용 언어: Python 3

$N \times M$ 크기의 배열로 표현되는 미로가 주어집니다. 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타냅니다. $(1, 1)$에서 출발하여 $(N, M)$의 위치로 이동할 때 지나야 하는 최소의 칸 수(최단 거리) 를 구하는 문제입니다.

💡 문제 접근 방법 (핵심 로직)

미로 찾기 문제에서 '최단 거리'를 구하라고 한다면, 깊이 우선 탐색(DFS)이 아닌 너비 우선 탐색(BFS) 을 사용하는 것이 정석입니다. BFS는 시작점에서 가까운 노드부터 차례대로(Level by Level) 탐색하기 때문에, 목적지에 도달하는 순간이 곧 최단 거리임이 보장되기 때문입니다.

1. 방향 벡터 설정: 다른 2차원 배열 탐색과 마찬가지로 dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]을 사용하여 상하좌우 이동을 제어합니다.
2. 거리 누적 기록 (In-place 수정): 이 문제의 가장 중요한 포인트입니다. 별도의 방문 처리 배열(visited)을 만들지 않고, 큐에서 새로운 좌표 (nx, ny)를 발견할 때마다 graph[nx][ny] = graph[x][y] + 1 과 같이 이전 좌표의 값에 1을 더해 줍니다.
   • 이렇게 하면 배열 자체에 출발지로부터의 거리가 기록되며, 값이 1보다 커지면 자연스럽게 "이미 방문한 곳"으로 취급되어 중복 방문을 막을 수 있습니다.
3. 조기 종료 (Early Exit): 탐색 중 (nx, ny)가 목적지인 (N-1, M-1)에 도달했다면, 더 이상 큐를 돌릴 필요 없이 계산된 값을 즉시 반환하여 실행 시간을 최적화합니다.

💻 코드 구현

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())

graph = [list(map(int, input().strip())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(start_x, start_y):
    queue = deque([(start_x, start_y)])
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 미로 범위 내에 있고, 갈 수 있는 길(1)인 경우
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:
                queue.append((nx, ny))
                
                # 핵심: 이전 칸의 거리 값에 1을 더하여 최단 거리 기록
                graph[nx][ny] = graph[x][y] + 1
                
                # 목적지에 도착하면 즉시 반환
                if nx == N - 1 and ny == M - 1: 
                    return graph[nx][ny]

print(bfs(0, 0))

🚨 트러블 슈팅 및 회고

• 최단 거리 문제에 DFS를 쓰면 안 되는 이유: 만약 이 문제를 DFS로 접근했다면, 운이 나쁠 경우 꼬불꼬불한 가장 먼 길을 먼저 탐색해 버릴 수 있습니다. 그러면 목적지에 도달하더라도 그것이 '최단 거리'인지 확신할 수 없어서 결국 모든 경로를 끝까지 다 탐색해야 하고, 이는 필연적으로 시간 초과(Time Out)로 이어집니다. 반면 BFS는 물결이 퍼지듯 거리가 1인 곳, 2인 곳, 3인 곳을 동시다발적으로 탐색하므로 처음 목적지를 마주친 순간이 최단 거리임을 100% 확신할 수 있다는 차이를 명확히 이해했습니다.
• 메모리 최적화: 2차원 배열 문제에서 습관적으로 visited 배열을 만들곤 했는데, 이렇게 입력받은 graph 배열의 데이터를 직접 가공(In-place 방식)하여 거리 배열과 방문 체크 배열 두 가지 용도로 동시에 활용하니 코드 라인 수도 줄고 메모리도 아낄 수 있어 매우 효율적이었습니다.