[Python] 백준 2206 벽 부수고 이동하기

1. 문제 링크

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

2206번: 벽 부수고 이동하기

---

2. 문제 요약

• 최단 경로 구하기 문제 → bfs 탐색
• 벽을 1개까지만 부수고 이동 가능 → 최단경로에서 이 조건으로 어려워짐.

 

---

3. 아이디어 정리

아이디어 1. 벽을 모두 부수면서 모든 경우의 수를 확인

⇒ 시간 초과

아이디어 2. 벽을 부순 상태와 부수지 않은 상태의 visit 값을 분리하기

1. 벽을 부순 상태와 부수지 않은 상태 분리

visit_0 = [[0] * m for _ in range(n)]  # 부수지 않은 상태 최단거리
visit_1 = [[0] * m for _ in range(n)]  # 부순 상태 최단거리

 

2. 현재까지 벽을 부순 상태

• 벽이 x & visit_1(부순 상태 변수) 방문 안 한경우, 거리 저장 & 큐에 넣기

 

3. 현재까지 벽을 부순적 없는 상태

• 새로운 벽을 만난 경우 ⇒ visit_1 [nx][ny]에 방문을 안 하면 거리 저장 & 큐에 넣기
• 벽이 없는 곳을 간 경우 ⇒ visit_0[nx][ny]에 방문을 안 하면 거리 저장 & 큐에 넣기

---

4. 문제 풀이

4-1. 내 풀이

import sys
import copy
from collections import deque

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

def bfs():
    visit_0 = [[0] * m for _ in range(n)]  # 부수지 않은 상태 최단거리
    visit_1 = [[0] * m for _ in range(n)]  # 부순 상태 최단거리
    visit_0[0][0] = 1        # 부수지 않은 상태 방문
    dq = deque([(0, 0, 0)])  # 좌표, 벽 부순 유무(0:부수지 않음)
    while dq:
        x, y, d = dq.popleft()
                # 마지막에 도달한 경우, 최단거리 리턴 
        if x == n - 1 and y == m - 1:
            if d == 0:
                return visit_0[x][y]
            else:
                return visit_1[x][y]

        for a in range(4):
            nx = dx[a] + x
            ny = dy[a] + y
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
                        # 1. 벽을 이미 부순 상태 
            if d == 1:  
                                # 벽이 x & 방문 안 한경우 
                if graph[nx][ny] == 0 and not visit_1[nx][ny]:
                    visit_1[nx][ny] = visit_1[x][y] + 1
                    dq.append((nx, ny, 1))
            else:   #  2. 아직 뚫어도 되는 상태
                # 2-1. 새로운 벽 발견
                if graph[nx][ny] == 1 and not visit_1[nx][ny]:
                    visit_1[nx][ny] = visit_0[x][y] + 1
                    dq.append((nx, ny, 1))
                # 2-2. 벽 없는 경우
                elif graph[nx][ny] == 0 and not visit_0[nx][ny]:
                    visit_0[nx][ny] = visit_0[x][y] + 1
                    dq.append((nx, ny, 0))
    else:
        return - 1

n, m = map(int, sys.stdin.readline().split())  # n * m
graph = list()
for x in range(n):
    graph.append([int(i) for i in sys.stdin.readline().rstrip()])

print(bfs())

---

5. 결론

• 어려운 bfs 문제 ☹️
• 벽을 부순 상태와 부수지 않은 상태의 visit 분리하는 것이 핵심인 문제