[백준 Python] 2206번 벽 부수고 이동하기 (BFS)

728x90

2206번 벽 부수고 이동하기 (BFS)

1. 문제

N x M 크기의 배열에서 (0,0)에서 (N-1, M-1)까지 이동하는 문제이다.

이동 중에 최대 한 번만 벽을 부수고 지나갈 수 있다.
최소 몇 번의 이동으로 목표 지점에 도달할 수 있는지 구해야 한다.

입력: 첫째 줄에 N, M (1 ≤ N, M ≤ 1000)
지도: 0은 이동할 수 있는 길, 1은 벽
출력: 목적지까지 이동할 수 있는 최단 거리. 이동할 수 없다면 -1 출력.

문제 접근 방법

최단 경로를 찾는 문제 → BFS
벽을 부수는 경우와 부수지 않는 경우를 모두 탐색하기 위해 ⭐️ 3차원 visited 배열 사용 ⭐️

2. 풀이 과정

🔍 문제 분석

BFS는 각 지점에서 인접한 지점들을 모두 탐색하므로 최단 경로를 찾는 데 효과적이다.
벽을 부쉈는지 여부를 기록하여 경로를 탐색해야 하므로, visited 배열을 visited[row][col][broken] 형태로 구성한다.
- broken == 0: 벽을 부수지 않고 방문한 경우
- broken == 1: 벽을 부수고 방문한 경우

visited 배열 ⭐️
- visited[row][col][broken] 형태로 구성하여 벽을 부수고 방문한 경우와 부수지 않고 방문한 경우를 분리해서 기록한다.
- 벽을 부수고 이동하는 경우(broken == 1)는 더 이상 벽을 부술 수 없으므로, 방문 처리를 다르게 해야 한다.
큐 사용 (BFS 구현)
- 큐에 (현재 행, 현재 열, 이동 거리, 벽을 부순 횟수)를 저장한다.
- 벽을 부수지 않았을 때(broken == 0)와 벽을 부수었을 때(broken == 1)를 모두 관리.
조건 처리
- 이동할 수 있는 길(0)인 경우, 현재 상태로 큐에 추가한다.
- 벽(1)인 경우, 아직 벽을 부순 적이 없으면 큐에 추가한다.
- 목적지에 도달하면 이동 거리를 출력하고 종료한다.

3. 코드

import sys
from collections import deque

input = sys.stdin.readline

def bfs(n, m, mymap):
    # 방향 벡터 (상, 하, 좌, 우)
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]

    # 방문 배열: visited[row][col][broken]
    visited = [[[False] * 2 for _ in range(m)] for _ in range(n)]

    # 시작 지점 설정
    que = deque([(0, 0, 1, 0)])  # (row, col, 이동 횟수, 벽을 부순 횟수)
    visited[0][0][0] = True

    while que:
        r, c, dist, broken = que.popleft()

        # 목표 지점 도달 시 거리 반환
        if r == n - 1 and c == m - 1:
            return dist

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]

            if 0 <= nr < n and 0 <= nc < m:
                # 이동할 수 있는 길인 경우
                if mymap[nr][nc] == 0 and not visited[nr][nc][broken]:
                    visited[nr][nc][broken] = True
                    que.append((nr, nc, dist + 1, broken))

                # 벽인 경우 (부순 적이 없는 경우에만 부술 수 있음)
                if mymap[nr][nc] == 1 and broken == 0 and not visited[nr][nc][1]:
                    visited[nr][nc][1] = True
                    que.append((nr, nc, dist + 1, 1))

    return -1


# 입력 처리
n, m = map(int, input().split())
mymap = [list(map(int, input().strip())) for _ in range(n)]

# 결과 출력
print(bfs(n, m, mymap))

코드 설명

최적화 포인트

방문 배열을 2차원이 아닌 3차원으로 구성하여 불필요한 중복 탐색 방지
큐를 사용하여 BFS를 구현함으로써 최단 경로를 빠르게 탐색

시간 복잡도

최악의 경우 모든 칸을 방문하므로 O(N × M)이다.
하지만 visited 배열을 효율적으로 사용하여 중복 방문을 방지한다.

4. 결과

벽을 부수고 이동하는 경우와 그렇지 않은 경우를 동시에 관리하는 것이 핵심이다. BFS 방식으로 문제를 풀 때, 상태를 구분하여 관리하는 방법을 확실히 이해할 수 있었다.