[백준 9376] 탈옥 - 0-1 BFS 알고리즘

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

9376번: 탈옥

문제

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오. 문을 한 번 열면 계속 열린 상태로 있는다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.

 

 

 

---

아이디어를 떠올리는 것이 어려운 문제였다.

열어야 하는 문의 최솟값을 찾아야 한다는 점이 최소 거리를 찾는 문제 유형에 해당되는데, 여는 문의 개수를 표시할 때의 이동시 가중치는 0 또는 1이므로 0-1 BFS 알고리즘을 적용할 수 있다.

 

1. 감옥 바깥에서 안으로 들어갈 수 있는 위치를 찾는 알고리즘이 복잡하므로 감옥 바깥쪽에 빈 공간인 '.'들을 배치한다.
2. 이 문제는 죄수 두 명을 탈옥시키기 위해 접근해서 열어야 하는 문의 최소 개수를 구해야 한다. 죄수 두 명을 찾기 위해 한번에 bfs를 진행하면 오답이 나오기 때문에 (0, 0), 죄수1, 죄수2의 위치들 각각으로부터 출발하여 따로 감옥 전체 탐색을 진행한다.
3. 또하나 신경써야 할 점은 방문할 위치의 우선순위이다. 처음 -1로 초기화되어 있던 visited는 열어온 문의 최소 개수를 담는 변수이다. '#'인 곳에 방문하기 위해서는 이전 위치보다 1 더 많은 개수로 방문해야 하고, '.'나 '$'인 곳에 방문하기 위해서는 이전 위치의 개수로 방문해야 한다. 0의 이동 가중치를 갖는 위치는 덱의 front에 삽입하고, 1의 이동 가중치를 갖는 위치는 덱의 back에 삽입하면 정확하게 최소 개수들을 구할 수 있다.
4. 감옥 전체를 전체 탐색하며 어떠한 위치를 (0, 0), 죄수1, 죄수2의 위치 각각에서 출발하여 만든 탐색 결과들에서 모두 방문했을 때의 그 합을 더하고 '#' 벽을 발견할 경우 3번의 카운트 수가 겹치므로 2를 뺀다. 결과값들 중 가장 최솟값이 열어야 하는 문의 최솟값이다.

 

 

<< 전체 코드 >>

import sys
from collections import deque
input = sys.stdin.readline

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


def bfs(y, x):
    visited = [[-1 for _ in range(w+2)] for _ in range(h+2)]
    q = deque([[y, x]])
    visited[y][x] = 0

    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if ny < 0 or ny >= h+2 or nx < 0 or nx >= w+2:
                continue
            if visited[ny][nx] == -1:
                if board[ny][nx] == '#':
                    visited[ny][nx] = visited[y][x] + 1
                    q.append([ny, nx])
                elif board[ny][nx] in ['.', '$']:
                    visited[ny][nx] = visited[y][x]
                    q.appendleft([ny, nx])

    return visited


t = int(input())
for _ in range(t):
    answer = int(2e9)
    h, w = map(int, input().split())
    board = [['.' for _ in range(w+2)] for _ in range(h+2)]
    persons_pos = []
    for i in range(h):
        row = input().rstrip()
        for j in range(w):
            board[i+1][j+1] = row[j]
            if board[i+1][j+1] == '$':
                persons_pos.append((i+1, j+1))

    dp1 = bfs(0, 0)
    y, x = persons_pos.pop()
    dp2 = bfs(y, x)
    y, x = persons_pos.pop()
    dp3 = bfs(y, x)

    for i in range(h+2):
        for j in range(w+2):
            if dp1[i][j] != -1 and dp2[i][j] != -1 and dp3[i][j] != -1:
                res = dp1[i][j] + dp2[i][j] + dp3[i][j]
                if board[i][j] == '#':
                    res -= 2
                answer = min(answer, res)

    print(answer)