[백준/9376/파이썬] 탈옥

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

9376번: 탈옥

Problem

• 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.
• 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

조건

• 문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다.
• 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오. 문을 한 번 열면 계속 열린 상태로 있는다.
• 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
• 첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.
• 상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

SOL

 

단순히 BFS를 쓰면 안되는 문제이다. 처음에, BFS를 돌면서, visited에 문열었던 갯수를 기록하고, 자기자신 +그 이전에 문 열었던 갯수를 해서,최솟값을 구해주려고 했다.

 

단순한 BFS로 구현한다면, 2가지 문제점이 발생한다.

 

1. 문을 안열고 나올 수 있는 방법이 있다면, 문을 열지 않고 나와야한다.

아래 예저처럼, 문을 열지 않고도 빠져 나올 수 있다면,  0개가 나와야하는데, deque는 bfs의 거리(edge)의에 따라 도는 친구이므로, 문을 1개를 여는 경우의 수가 먼저 튀어나오게 된다.  이 문제는, "#"인 경우 우선도를 뒤로 보내주면 된다. 즉, "." or"$"일때, dq에 먼저 넣어주면 되는 문제이다. ( "0-1 BFS" 라는 유형이라고 한다.. 찾아봐서 알게 되었다)

5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*

2. 둘이 같이 탈출하면 문의 갯수가 적어지는데, 따로 탈출해버리는 경우가 생겨버린다.

(4번은 개인주의야!)

각각의 범죄자가 최단경로로 탈출한다면,  개인은 문을 5개로 최소한으로 열었지만, 전체적으로 보면 10개가 열린 상황이 되버리고, 둘이 같이 탈출을 하게 된다면,(중간길)을 통해서 9개만 열면 되는 상황이 펼쳐진다.

그림판에서 그려옴

즉, 일반적인 BFS로는 풀 수 없는 문제가 되버렸다.

 

제 3자의 등장

• 갑자기 형이 왜나와?라고 할 수 있지만, 천천히 설명을 들어보면 이해가 간다.
• 이번 문제를 해결하기 위해서는 두 죄수이외의 제삼자를 도입해야 한다.
• 바로 감옥의 밖에서 각 죄수로의 최단 경로(최소 개수의 문을 여는 경로)를 이동하는 상근이이다.

우리는 3가지의 정보가 있으면, 최소한의 문만 열고 탈출 할 수 있게 된다.

왜나하면, 상근이 밖에서 최소의 문을 열고 들어올거고, 죄수 1도 최소의 문을 열거고, 죄수 2도 최소의 문을 열거다.

이때, 처음으로 만나는 시점이 바로, 우리가 최소한의 문만 열고 탈출 가능한 경우이다.

 

이때, 처음 만나는 시점을 알기위해서, 3가지 방문 배열의 정보가 필요하게 된다. 각각 2차원 배열의 i,j에 대응하는 값들의 합을 구해주고, "#"인 경우 합에서 2를 빼준다음(중복되므로), 그 값이 최소가 되는 순간이 처음 마주치는 경우이다. (문의 갯수의 정보만 알면 되므로, 사실 언제 딱 처음만났는지는 정확하게 반영되어있지 않지만, 어쨌든 확실한건, 문을 최소한으로 열고 우리는 만났다는 점이다)

 

아래의 예시로, 예를 들어보겠다.

9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********

1. 상근이가 밖에서 열고 들어온 문의 갯수를 기록한 visited 배열
2. 죄수 1이 안에서 밖으로 가기위해서, 열었던 문의 갯수를 기록한 visited 배열
3. 죄수 2가 안에서 밖으로 가기위해서, 열었던 문의 갯수를 기록한 visited 배열

상근이                                                                                              죄수 1

죄수 2

3가지 visited 배열을 각 좌표끼리 합한 값.(각각의 배열의 1칸은 만나는 시점을 의미한다고 볼 수도 있다)

위의 예시같은 경우에는, 밖에서 상근이가 열어놓은 문으로 죄수 1,죄수2가 만나서 나가면 되는 경우이다.

코드를 보면 더 이해가 잘 갈거다! (말로 하니까 표현이 엄청 이상해진다)

import sys
from collections import deque

T=int(input().rstrip())
dy=[0,1,0,-1]
dx=[1,0,-1,0]

def bfs(y,x):
    visited=[[-1 for _ in range(M+2)]for _ in range(N+2)]
    dq=deque()
    dq.append((y,x))
    visited[y][x]=0
    while dq:
        y,x=dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not(0<=ny<N+2 and 0<=nx<M+2):
                continue
            if visited[ny][nx] == -1:
                if board[ny][nx]=="." or board[ny][nx]=="$":
                    visited[ny][nx]=visited[y][x]
                    dq.appendleft((ny,nx))
                elif board[ny][nx]=="#":
                    visited[ny][nx]=visited[y][x]+1
                    dq.append((ny,nx))
    return visited

for _ in range(T):
    N,M=map(int,input().split())
    board=[list("."*(M+2))]
    for i in range(N):
        board.append(list('.'+input().rstrip()+'.'))
    board.append(list('.'*(M+2)))
    
    prisoner=[]
    for i in range(N+2):
        for j in range(M+2):
            if board[i][j]=="$":
                prisoner.append((i,j))
    
    one=bfs(prisoner[0][0],prisoner[0][1])
    two=bfs(prisoner[1][0],prisoner[1][1])
    sang=bfs(0,0)
    ans=sys.maxsize
    for i in range(N+2):
        for j in range(M+2):
            if one[i][j] != -1 and two[i][j] != -1 and sang[i][j] != -1:
                result=one[i][j]+ two[i][j] + sang[i][j]
                # 벽인 경우, pass해준다.
                if board[i][j]=="*":
                    continue
                # 문인 경우, 3명 중에 2명이 열고온건 중복되므로 빼준다.
                if board[i][j]=="#":
                    result-=2
                ans=min(ans,result)
    print(ans)