[백준 알고리즘] 2206번: 벽 부수고 이동하기 (Python / 파이썬)

---

문제 접근

최단 경로를 구하는 문제이므로 bfs가 적합하다.

n * m 행렬이 주어지고, 시작점이 정해져 있기에 생각보다 간단한 문제라고 생각했다.

벽(1)을 한 번만 부술 수 있으므로, 모든 벽들을 하나씩 부숴보고 bfs를 각각 돌려 최솟값을 구하면 된다고 생각했지만,

n , m <= 1,000 이므로, 단순히만 생각해도 벽이 최대 nm -2(시작,종료점)개 존재할 수 있어 bfs를 1,000,000번 수행해야 하므로 시간초과가 날 것이다.

 

따라서 visited 배열을 3차원으로 만들어 벽을 부수고 가고 있는 경로인지, 벽을 아직 부수지 않고 가고 있는 경로인지 체크하는 방법을 사용했다.

이렇게 하면 bfs를 한 번만 수행하고 문제를 풀 수 있다.

 

bfs는 다음과 같이 진행된다.

1. 큐에 시작점 추가
2. 큐가 있는 동안 반복
1) popleft 한 요소의 상하좌우 탐색 (이때, 종료지점 확인)
2) matrix[nx][ny]가 1인 경우 : 아직 1을 부수지 않았다면 부수기, 큐에 추가
3) matrix[nx][ny]가 0인 경우: 방문하지 않았다면 큐에 추가
3. 종료가 되지 않았다면 -1 리턴 (도달하지 못하는 경우)

최단 경로 계산은 이전 visited 값에 + 1 해주어 계산한다.

 

정답 코드

#2206번: 벽 부수고 이동하기

import sys
from collections import deque

def bfs(matrix, visited):
    queue = deque()
    queue.append((0, 0, 0))
    visited[0][0][0] = 1
    dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]

    while queue:
        x, y, z = queue.popleft()
        if x == n - 1 and y == m - 1:
            return visited[x][y][z]
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if matrix[nx][ny] == '1':
                    if z == 0:
                        queue.append((nx, ny, 1))
                        visited[nx][ny][1] = visited[x][y][0] + 1
                else:
                    if visited[nx][ny][z] == 0:
                        queue.append((nx, ny, z))
                        visited[nx][ny][z] = visited[x][y][z] + 1
    return -1

n, m = map(int, sys.stdin.readline().split())
matrix = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

visited = [[[0, 0] for _ in range(m)] for _ in range(n)]

print(bfs(matrix, visited))

---

2206번: 벽 부수고 이동하기