IT-garden

문제

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

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

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

입력

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

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

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

출력

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

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

t=int(input())

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

def bfs(s1,s2):
    ch=[[-1]*(w+2) for i in range(h+2)]
    de=deque()
    de.append([s1,s2])
    ch[s1][s2]=0

    while de:
        x,y=de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < h+2 and 0 <= ny < w+2:
                if ch[nx][ny] == -1:
                    if a[nx][ny] == '.' or a[nx][ny] == '$':
                        ch[nx][ny] = ch[x][y]
                        de.appendleft([nx,ny])
                        
                    if a[nx][ny] == '#':
                        ch[nx][ny] = ch[x][y] +1
                        de.append([nx,ny])
    return ch

while t:
    t -= 1
    h,w=map(int,input().split()) 

    a=[list('.'*(w+2))]
    for i in range(h):
        a.append(list('.'+input().strip()+'.'))
    a.append(list('.'*(w+2)))
    
    s=[]
    for i in range(h+2):
        for j in range(w+2):
            if a[i][j] == '$': # 죄수
                s.append([i,j])
    
    one=bfs(s[0][0],s[0][1])
    two=bfs(s[1][0],s[1][1])
    three=bfs(0,0)
    m=sys.maxsize
    
    for i in range(h+2):
        for j in range(w+2):
            r=one[i][j]+two[i][j]+three[i][j]

            if a[i][j] == '*':
                continue
            if a[i][j] == '#':
                r -= 2
            m=min(m,r)

    print(m)

이 문제에서 중요한 것은 문제에서 주어진 평면도에서 가로, 세로의 가장자리를 확대해서 답을 구한다는 것입니다.
가로, 세로를 확대해도 괜찮은 이유는 확대한 곳에는 문이 없기 때문에 따로 열어야 하는 문의 개수가 올라가지 않기 때문입니다.

one : 첫 번째 죄수가 출발해서 문을 여는 경우
two : 두 번째 죄수가 출발해서 문을 여는 경우
three : 밖에서 출발해서 문을 여는 경우

3가지 경우에 bfs를 통해 ch에 열어야 하는 문의 개수를 저장하고 리턴합니다.
bfs 과정에서 통과하려는 곳이 '.'인 경우 먼저 방문할 수 있게 appendleft를 이용합니다.

평면도의 각 위치에 대한 열어야 하는 문의 개수를 비교합니다.
위치가 '#'인 경우는 3명이 모두 문을 열었기 때문에 한명만 열면 모두 통과할 수 있기 때문에 -2를 합니다.
그 후 최소값을 구하여 출력합니다.

백준 알고리즘 9376번 : https://www.acmicpc.net/problem/9376