백준 9376 _ Python

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

9376번: 탈옥

문제

---

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

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

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

 

 

입력

---

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

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

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

 

출력

---

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

#예제 입력
3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********

# 예제 출력
4
0
9

 

접근법

---

1. 우선 BFS 문제 인데, 여러 가지를 시도해보다가 n, m을 입력받고, 죄수의 위치를 x1, y1, x2, y2로 선정해준다.
2. 그다음, d0, d1, d2라는 다른 map을 형성해주는데, 이는 각각
3. d0 -> 밖(0,0)에서 부터 죄수가 들어오는데 걸리는 거리 / d1-> (x1, y1)으로부터의 거리 / d2 ->(x2, y2)으로부터의 거리를 나타내게 된다. 
4. bfs를 이용하여 go를 만들어주는데 이때 , 거리가 가까운 것부터 차례대로 처리해줘야 하므로 만약 문을 지나지 않았다면, appendleft를 통하여 deque에 push 해준다.
5. 그다음 차례대로 돌면서 d0 + d1 + d2를 했을 때, 가장 최솟값을 찾아주는데 , 이때  d0 d1 d2는 a [i][j]가 벽이 아닐때 그리고, d [i][j] 또한 -1 이 아니어서 세 개가 모두 가능한 경로의 값이어야 한다.

추가로 왜 밖에서 온 경우를 생각해주는 지 물어볼 텐데, 이는 죄수 2명이 만나서 이동하여 밖으로 나가는 경우의 수를 거꾸로 생각해준 것이다. 예를 들어 i, j에서 d0+ d1 + d2 가 최소가 되었으면, 이는 죄수 1이 x1, y1 -> i, j(d1[i][j])로 가는 경우의 수 + 죄수 2가 x2, y2 -> i, j(d2[i][j])로 가는 경우의 수 + i, j에서 밖으로 나가는 경우의 수(d0 [i][j]) 를 더한 값을 의미하게 된다.

 

 

from collections import deque

dx=[0,0,1,-1]
dy=[1,-1,0,0]
def go(a,x,y):
    n = len(a)
    m = len(a[0])
    dist = [[-1]*m for _ in range(n)]
    q = deque()
    q.append((x,y))
    dist[x][y]=0
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]
            if 0<=nx<n and 0<=ny<m and dist[nx][ny]==-1 and a[x][y]!='*':
                if a[nx][ny]=='#':
                    dist[nx][ny]=dist[x][y]+1
                    q.append((nx,ny))
                else:
                    dist[nx][ny]=dist[x][y]
                    q.appendleft((nx,ny))
    return dist

t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    a = ['.'+input()+'.' for _ in range(n)]
    n+=2
    m+=2
    a=['.'*m]+a+['.'*m]
    d0 = go(a,0,0)
    x1=y1=x2=y2=-1
    for i in range(n):
        for j in range(m):
            if a[i][j]=='$':
                if x1==-1:
                    x1,y1=i,j
                else:
                    x2,y2=i,j
    
    d1 = go(a,x1,y1)
    d2 = go(a,x2,y2)
    ans = n*m

    for i in range(n):
        for j in range(m):
            if a[i][j] == '*': continue
            if d0[i][j] == -1 or d1[i][j] == -1 or d2[i][j] == -1: continue
            cur = d0[i][j] + d1[i][j] + d2[i][j]
            if a[i][j] == '#': cur -=2
            ans = min(ans,cur)
    print(ans)