백준 2178 미로 탐색 | 좌표형 BFS 구현과 최단거리 풀이

백준 2178은 그냥 좌표형 BFS 최단거리 문제다.

핵심은 복잡하지 않다.

(0, 0)에서 시작해서 BFS로 한 칸씩 퍼져 나가면서, 처음 도달한 값이 곧 최단거리라는 점만 잡으면 된다.

다만 이 문제는 일반 그래프 BFS랑 다르게

노드가 숫자 하나가 아니라 좌표 (x, y) 라는 점,

그리고 인접 노드를 인접 리스트가 아니라 상하좌우 직접 계산으로 찾는다는 점에서 한 번 헷갈리기 쉽다.

나도 처음엔 BFS라는 건 바로 보였는데,

막상 구현할 때는

• 좌표를 큐에 어떻게 넣을지
• 방문 체크를 따로 할지
• 거리 기록을 어디에 할지

이 부분에서 한 번씩 생각을 더 하게 됐다.

이번 글은 이 문제를 기준으로

좌표형 BFS를 어떻게 구현하는지 정리해보려고 한다.

---

🔗 문제 링크

백준 2178 - 미로 탐색

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

---

문제 정리

문제 조건은 이렇다.

• 1은 이동 가능한 칸
• 0은 이동 불가능한 칸
• 시작점은 (0, 0)
• 도착점은 (N-1, M-1)
• 지나야 하는 칸 수의 최솟값을 구해야 한다

여기서 바로 봐야 하는 건 이것들이다.

• 최단거리
• 격자
• 상하좌우 이동
• 가중치 없음

이 조합이면 그냥 BFS로 가면 된다.

---

✅ 핵심 아이디어

이 문제는 이렇게 보면 된다.

1. 미로를 2차원 리스트로 받는다
2. BFS 큐에는 (x, y) 좌표를 넣는다
3. 상하좌우 4방향을 보면서 이동 가능한 칸을 찾는다
4. 처음 도달한 칸은 현재 칸 값 + 1로 갱신한다
5. 마지막 graph[n-1][m-1] 값이 최단거리다

즉, 이 문제는

그래프 BFS를 좌표형 BFS로 바꿔서 쓰는 문제다.

---

정답

from collections import deque

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]

q = deque()
q.append((0, 0))

while q:
    x, y = q.popleft()

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

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue

        if graph[nx][ny] == 0:
            continue

        if graph[nx][ny] == 1:
            graph[nx][ny] = graph[x][y] + 1
            q.append((nx, ny))

print(graph[n - 1][m - 1])

---

생각해야 하는 부분

이 문제는 BFS라고 끝나는 게 아니라,

일반 그래프 BFS랑 뭐가 다른지를 먼저 봐야 한다.

1. 노드는 도시 번호가 아니라 좌표다

일반 그래프 문제에서는 보통 큐에 이런 게 들어간다.

q.append(1)

근데 미로 탐색은 그게 아니다.

이 문제에서 노드는 미로의 한 칸이다.

즉 큐에 들어가는 건 정수 하나가 아니라 좌표 두 개다.

q.append((0, 0))

이 문제를 제대로 풀려면

애초에 노드를 “숫자”로 보지 말고 위치 정보로 보는 게 중요하다.

---

2. 인접한 곳은 인접 리스트가 아니라 직접 계산한다

그래프 문제에서는 보통 이런 식으로 간다.

for nxt in graph[now]:
    ...

근데 미로 탐색은 인접 리스트가 없다.

상하좌우 4칸을 직접 계산해야 한다.

그래서 dx, dy를 둔다.

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

그리고 현재 위치 (x, y)에서 다음 위치 (nx, ny)를 만든다.

nx = x + dx[i]
ny = y + dy[i]

즉, 이 문제는 인접 노드를 직접 생성하는 BFS다.

---

3. 거리 기록은 graph 자체에 바로 한다

이 문제는 별도의 distance 배열을 만들 수도 있다.

근데 이 문제에서는 graph 자체를 재활용하는 방식이 훨씬 자주 쓰인다.

핵심은 이 줄이다.

graph[nx][ny] = graph[x][y] + 1

현재 칸까지의 거리 값이 이미 들어 있으니까,

새로 도달한 칸은 거기서 +1 하면 된다.

즉,

• 원래 1은 그냥 “갈 수 있다”는 뜻인데
• BFS가 진행되면서 그 칸은 “최단거리 값”으로 바뀐다

이 구조다.

이게 이 문제에서 제일 깔끔한 포인트다.

---

4. 처음 도달한 값이 곧 최단거리다

이건 BFS 문제에서 항상 중요하다.

BFS는 가까운 칸부터 순서대로 퍼져 나가기 때문에,

어떤 칸에 처음 도달했을 때의 거리가 곧 최단거리다.

그래서

if graph[nx][ny] == 1:

이 조건이 중요하다.

아직 방문 안 한 길만 갱신해야

가장 먼저 도달한 값이 유지된다.

---

예외처리 / 주의할 점

⚠️ 1. 범위 체크를 먼저 해야 한다

격자 문제는 무조건 이게 먼저다.

if nx < 0 or nx >= n or ny < 0 or ny >= m:
    continue

범위 밖으로 나간 좌표를 먼저 걸러내지 않으면

인덱스 에러가 바로 난다.

이건 좌표형 문제에서 거의 기본이다.

---

⚠️ 2. 0은 갈 수 없는 칸이다

if graph[nx][ny] == 0:
    continue

이 문제에서 0은 벽이다.

즉, 이동 대상이 아니다.

1만 이동 가능한 칸이다.

이 부분을 그냥 “숫자니까 방문 가능 여부” 정도로 애매하게 보면 헷갈린다.

이 문제는 값 의미를 명확하게 봐야 한다.

• 0 → 벽
• 1 → 아직 방문 안 한 길
• 2 이상 → 방문했고, 거리 기록됨

BFS가 돌고 나면 의미가 이렇게 바뀐다.

---

⚠️ 3. 시작점 값이 1이라는 걸 이용한다

문제에서 시작점 (0, 0)은 무조건 1이다.

그래서 BFS를 시작하면 자연스럽게 거리 기준점 역할을 한다.

즉,

• 시작점은 1
• 다음 칸은 2
• 그다음은 3

이런 식으로 누적된다.

그래서 마지막에 graph[n-1][m-1]를 출력하면

그게 곧 최소 칸 수가 된다.

---

⚠️ 4. 큐는 리스트보다 deque가 맞다

이 문제도 BFS이기 때문에 큐가 필요하다.

리스트의 pop(0)으로도 돌릴 수는 있지만,

앞에서 계속 꺼내는 구조라 deque가 더 맞다.

from collections import deque
q = deque()
q.append((0, 0))
x, y = q.popleft()

이건 이제 그냥 습관처럼 가져가는 게 낫다.

---

내 시행착오

이 문제에서 내가 처음 헷갈린 건 크게 세 가지였다.

1. 일반 그래프 BFS처럼 보려고 했다

처음엔 BFS라는 건 바로 보였는데,

무의식적으로 “노드 번호” 같은 감각으로 접근했다.

근데 이 문제는 노드가 번호가 아니라 좌표다.

이걸 먼저 바꾸고 들어가야 했다.

---

2. 방문 배열을 따로 둘까 고민했다

처음엔 visited 배열을 따로 둘까 생각했다.

근데 이 문제는 graph 자체를 거리 기록용으로 덮어쓰는 방식이 더 깔끔했다.

graph[nx][ny] = graph[x][y] + 1

이렇게 하면

• 방문 체크
• 거리 기록

을 동시에 해결할 수 있다.

따로 배열 하나 더 두는 것보다 구조가 단순하다.

---

3. dx, dy가 처음엔 좀 어색했다

좌표형 문제를 자주 안 풀었을 때는

dx, dy가 괜히 낯설다.

근데 결국 하는 일은 단순하다.

• 위로 한 칸
• 아래로 한 칸
• 왼쪽 한 칸
• 오른쪽 한 칸

이걸 배열로 정리한 것뿐이다.

이걸 익숙하게 가져가야

미로 탐색, 섬 개수, 빙산, 토마토 같은 격자 문제들이 훨씬 쉬워진다.

---

한 줄 정리

이 문제는 좌표형 BFS의 기본형이다. 핵심은 큐에 좌표를 넣고, graph 자체를 거리 배열처럼 재사용하는 것이다.