[코딩테스트, 더 이상 미룰 수 없다] BOJ 2206 벽 부수고 이동하기 — BFS에서 상태 확장(state expansion) 이해하기

이 문제는 단순한 BFS처럼 보이지만, 실제로는 상태(state)를 확장해야 하는 BFS 문제이다.
처음 문제를 읽고 바로 구현하기보다는 다음과 같은 사고 과정을 통해 접근하였다.

---

1. 문제 유형 판단

문제의 핵심 조건은 다음과 같다.

• (1,1) → (N,M)으로 이동
• 상하좌우 이동
• 최단 경로
• 벽을 한 번만 부술 수 있음

여기서 가장 먼저 확인한 것은 다음 질문이었다.

이 문제는 최단거리 문제인가?

답은 YES였다.

이동 비용은 모두 동일하고, 목표는 가장 적은 칸을 지나가는 경로이다.
이 경우 그래프 이론에서 가중치가 동일한 최단거리 문제 → BFS로 해결할 수 있다.

 

---

2. 일반적인 BFS 설계

일반적인 격자 BFS는 다음과 같은 상태를 가진다.

(y, x)

그리고 방문 배열은

visited[y][x]

형태로 관리한다.

기본 구조는 다음과 같다.

while queue:
    현재 위치 꺼냄
    상하좌우 이동
    방문 안 했으면 queue에 추가

여기까지는 일반적인 미로 탐색 BFS와 동일하다.

---

 

3. 문제의 핵심: 같은 좌표라도 상태가 다르다

이 문제를 풀면서 가장 중요한 질문이 하나 생겼다.

같은 좌표에 도착했더라도 "벽을 부쉈는지 여부"에 따라 이후 행동이 달라지지 않을까?

예를 들어 (2,3) 위치에 도착했다고 하자.

하지만 다음 두 경우는 완전히 다르다.

1️⃣ 벽을 아직 안 부수고 도착한 경우

(2,3,0)

→ 앞으로 벽을 한 번 부술 수 있음

 

2️⃣ 이미 벽을 부수고 도착한 경우

(2,3,1)

→ 더 이상 벽을 부술 수 없음

즉 같은 좌표라도 서로 다른 상태이다.

따라서 기존의 방문 배열

visited[y][x]

로는 구분할 수 없다.

---

 

4. 상태(state) 확장

이 문제를 해결하기 위해 BFS 상태를 다음과 같이 확장하였다.

(y, x, broken)

여기서

broken = 0  → 아직 벽 안 부숨
broken = 1  → 이미 벽 부숨

이 상태를 관리하기 위해 방문 배열도 다음처럼 바뀐다.

visited[y][x][2]

또는

dist[y][x][2]

이렇게 하면 같은 좌표라도

(y,x,0)
(y,x,1)

을 서로 다른 상태로 관리할 수 있다.

---

 

5. 다음 상태 생성 규칙

현재 상태가

(y, x, broken)

일 때 상하좌우를 확인한다.

1️⃣ 다음 칸이 빈칸(0)

그대로 이동 가능하다.

(y, x, broken)
→
(ny, nx, broken)

---

2️⃣ 다음 칸이 벽(1)

이 경우 조건이 붙는다.

• 아직 벽을 안 부쉈다면 → 부수고 이동 가능
• 이미 벽을 부쉈다면 → 이동 불가

즉

벽 && broken == 0
→
(ny, nx, 1)

이렇게 상태가 변경된다.

---

 

6. "부술 가치가 있는 벽인가?"는 판단할 필요 없다

문제를 풀면서 다음 의문도 들었다.

미리 "부술 가치가 있는 벽인지" 판단해야 하지 않을까?

하지만 BFS에서는 그런 판단이 필요 없다.

벽을 만났을 때

• 아직 벽을 안 부쉈다면
• 일단 부수는 상태를 큐에 넣어본다

이 경로가 막다른 길이라면 자연스럽게 탐색이 종료된다.

즉 BFS는 가능한 상태를 모두 확장하면서 불필요한 경로를 자연스럽게 제거한다.

따라서 별도의 사전 분석 없이도 해결 가능하다.

---

 

7. BFS 구조 자체는 변하지 않는다

이 문제를 풀면서 BFS가 복잡해 보일 수 있지만
사실 구조는 완전히 동일하다.

기본 BFS

while queue:
    node = queue.popleft()

    for next in graph[node]:
        ...

격자 BFS

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

    for 4방향:
        ...

벽 부수기 BFS

while queue:
    y, x, broken = queue.popleft()

    for 4방향:
        ...

단지 상태(state)가 하나 더 추가된 것뿐이다.

---

 

8. 이 문제의 핵심 정리

이 문제의 핵심은 다음 한 문장으로 정리된다.

같은 좌표라도 "벽을 부쉈는지 여부"에 따라 다른 상태로 취급해야 한다.

따라서 BFS 상태를

(y, x, broken)

으로 확장하고

visited[y][x][2]

형태로 관리하면 해결할 수 있다.

---

 

 

마무리

 

BFS에서 "상태(state)"를 어떻게 설계하는가

를 이해하는 문제였다.

좌표만을 상태로 보는 것이 아니라

(좌표, 추가 조건)

까지 포함해 생각하는 것이 중요하다는 것을 배울 수 있었다.