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

문제 보기

 

BFS + 우선순위 큐를 활용하여 구현하였다.

 

맵이 주어졌을 대, 최단 경로를 구하는 것이 최종 목표이다.

벽을 부술 수 없으면 간단한 BFS 구현 문제이지만 벽을 1개 부술 수 있다는 것이 핵심이었다.

 

(0, 0)에서 중간 지점(4, 4)에 도달하는 방법이 2가지가 있을 때(벽을 부수고 왔을 때, 벽을 부수지 않고 왔을 때) 이 2가지 방법을 동일하게 생각하면 안 된다. 이후에 또 벽을 만나는 경우에 결괏값이 다르기 때문이다. 따라서 벽에 따른 방문 체크를 따로 관리하였다.

 

우선순위 큐는 거리가 제일 짧은 경로들을 계속적으로 업데이트하여 목표 지점에 도달하기 위해서 사용하였다.

 

알고리즘 설계는 아래와 같다.

1. (1, 0, 0, 0)를 우선순위 큐에 삽입한다. (거리, 좌표, 벽 플래그)

2. 우선순위 큐에서 pop 한 후 상, 하, 좌, 우로 움직인다.

 - 더 짧은 경우 업데이트한다.

3. 목표 지점에 도달하면 종료한다.

코드

import sys
import heapq

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


def bfs():
    q = []
    visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]  # 벽을 부순거랑, 부수지 않은 거 상황을 구분해야 한다.
    heapq.heappush(q, (1, 0, 0, 0))  # 거리, x, y, flag(벽)
    visited[0][0][0] = True

    while q:  # q가 빌 떄까지 반복
        cnt, x, y, flag = heapq.heappop(q)
        if x == n - 1 and y == m - 1:  # 목표 지점 도달
            return cnt
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if array[nx][ny] == 0:  # 빈칸
                    if visited[nx][ny][flag] == 0:
                        visited[nx][ny][flag] = 1
                        heapq.heappush(q, (cnt + 1, nx, ny, flag))
                elif array[nx][ny] == 1:
                    if not flag and visited[nx][ny][True] == 0:
                        visited[nx][ny][flag] = 1
                        heapq.heappush(q, (cnt + 1, nx, ny, True))
    return -1


if __name__ == "__main__":
    n, m = map(int, input().split())  # 맵의 크기 입력받기
    array = [list(map(int, input().strip())) for _ in range(n)]

    # bfs 탐색
    answer = 1e9
    answer = bfs()

    print(answer)