지난주 스터디에서 한 명이 이렇게 말했다. "다익스트라 코드는 맞는데, 왜 답이 안 나와?" 문제를 보니 '벽을 K개까지 부술 수 있다'는 조건이 붙어 있었다. 그 순간 깨달았다. 이건 단순 최단 경로가 아니라, 상태 공간 자체가 다른 문제다.
dist 배열에 차원을 추가하라
보통 최단 경로를 배우면 dist[v]를 쓴다. 정점 v까지의 최소 비용. 그런데 "벽을 최대 3개 부술 수 있다"는 조건이 붙는 순간, 같은 정점이라도 벽을 0개 부쉈을 때와 2개 부쉈을 때는 완전히 다른 상황이다. dist[v] 하나로는 이 차이를 담을 수 없다.
해법은 의외로 단순하다. dist[v][k] — "정점 v에, 벽을 k개 부순 채로 도착했을 때의 최소 거리". 차원을 하나 늘리는 것. 이게 전부다.
그래프의 정점 수가 N이고 부술 수 있는 벽이 K개라면, 실질적인 상태 수는 N × (K+1)이 된다. 시간복잡도가 O(N·K·log(N·K))까지 올라가긴 하지만, K가 보통 10 이하라서 실전에서 문제없이 돌아간다.
백준 14442로 손에 익히기
백준 14442번 "벽 부수고 이동하기 2"가 이 패턴의 교과서 같은 문제다. N×M 격자에서 (1,1)부터 (N,M)까지 최단 경로를 구하되, 벽을 최대 K개 부술 수 있다.
핵심 아이디어를 풀어 보면:
상태를
(행, 열, 부순 벽 수)로 정의한다dist[r][c][k]= 벽을 k개 부수고 (r,c)에 도달하는 최소 이동 횟수벽이 아닌 칸으로 이동하면 k를 유지한다
벽인 칸으로 이동하면 k를 1 올린다 (k < K일 때만 가능)
간선 가중치가 전부 1이므로 사실 BFS가 더 적절하다. 하지만 "상태를 확장한다"는 사고방식 자체가 다익스트라적이고, 가중치가 달라지는 변형에도 그대로 적용되니까 여기서 확실히 잡아두는 게 좋다.
from collections import deque
def solve():
N, M, K = map(int, input().split())
grid = [input().strip() for _ in range(N)]
INF = float('inf')
dist = [[[INF] * (K + 1) for _ in range(M)] for _ in range(N)]
dist[0][0][0] = 1
dq = deque([(0, 0, 0)])
while dq:
r, c, k = dq.popleft()
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < M:
# 빈 칸 → 벽 부수기 횟수 유지
if grid[nr][nc] == '0' and dist[nr][nc][k] > dist[r][c][k] + 1:
dist[nr][nc][k] = dist[r][c][k] + 1
dq.append((nr, nc, k))
# 벽 → 부수기 횟수 1 증가
elif grid[nr][nc] == '1' and k < K and dist[nr][nc][k+1] > dist[r][c][k] + 1:
dist[nr][nc][k+1] = dist[r][c][k] + 1
dq.append((nr, nc, k + 1))
ans = min(dist[N-1][M-1][j] for j in range(K + 1))
print(ans if ans < INF else -1)
solve()가중치가 1이 아닌 문제라면 deque 대신 heapq를 쓰면 된다. dist 배열에 차원을 추가하는 핵심 구조는 똑같다.
이 패턴이 숨어 있는 다른 유형들
벽 부수기만 이런 게 아니다. 의외로 자주 마주친다.
열쇠와 문 (백준 1194) — 열쇠 종류를 비트마스크로 표현한다. dist[r][c][keys]에서 keys는 비트. 열쇠가 6종이면 상태가 64배로 뛴다.
낮/밤 전환 — 이동할 때마다 시간대가 바뀌고, 특정 칸은 밤에만 지나갈 수 있다면? dist[r][c][time % 2].
체력·연료 제한 — 이동마다 체력이 줄고, 특정 지점에서 회복 가능. 잔여 체력을 상태에 포함시킨다.
공통점은 하나다. 이동 가능 여부나 비용이 지금까지의 행동에 따라 달라진다면, 좌표만으로는 현재 상황을 특정할 수 없다. 그때 상태를 하나 더 얹는다.
실전에서 삐끗하는 지점들
패턴 자체는 어렵지 않은데, 디테일에서 자주 틀린다.
첫째, dist 초기화 누락. 차원이 늘어나면 초기화도 한 겹 더 들어간다. 3차원 배열을 INF로 채우는 걸 빼먹으면 첫 번째 테스트케이스부터 엉뚱한 값이 튀어나온다.
둘째, 답을 구할 때 모든 k에 대해 min을 취해야 한다. dist[N-1][M-1][K]만 보는 실수가 정말 많다. 벽을 덜 부수고 도착하는 경로가 더 짧을 수 있다는 걸 잊지 말자.
셋째, 상태 수 폭발. N=1000에 K=10이면 상태 천만 개 — 괜찮다. 그런데 N=1000에 열쇠 15개면? 상태가 3천만 개를 훌쩍 넘는다. 이 수준이면 다른 접근을 고민해야 한다. 문제를 읽고 상태 수를 대략 곱셈으로 어림잡는 습관을 들이자.
마지막으로, 방문 체크 타이밍. BFS에서 큐에 넣을 때 체크할지, 뺄 때 체크할지에 따라 속도 차이가 크다. 넣을 때 체크하는 편이 중복 삽입을 원천 차단해서 일반적으로 빠르다. 위 코드도 그렇게 짜여 있다.
카카오든 네이버든, "최단 경로 + 뭔가 조건"이 보이면 일단 상태를 어떻게 정의할지부터 생각하라. 알고리즘이 어려운 게 아니라, 상태 설계를 안 해서 못 푸는 거다.