[BaekJoon] 9376 탈옥

🔦 문제 링크

✍️ 나의 풀이

---

일반적인 BFS와 문제풀이 방법이 다르며 아이디어가 필요했다. 죄수들이 문을 열며 탈출하는 경우가 있고 상근이가 죄수들을 구하러 가는 3가지 시나리오가 있다고 생각해보자.

1. 첫번째 죄수가 문을 열고 나오는 경우
2. 두번째 죄수가 문을 열고 나오는 경우
3. 상근이가 죄수를 구하러 가는 경우

이 3가지 경우를 BFS를 통해 문을 여는 최솟값을 구해야 한다.

1번과 2번만 구해서 문을 여는 최솟값을 구하려면 공통으로 문을 여는 경우가 없어야 한다.

3번의 경우가 필요한 이유는 공통으로 문을 여는 경우가 필요하기 때문이다.
1번과 2번은 각자 자신의 문을 열고 나와서 공통의 문을 만나게 되고 그 문이 최소가 되는 값을 찾는 것이 이 문제의 핵심이다.

< 중요 포인트 >

• 문은 한번만 열면 되므로 중복되는 횟수를 빼준다.
• 문을 여는 최솟값을 구해야 하므로
  1. 문을 열지 않는 경우를 먼저 데크의 앞에 넣어 진행시킨다.
  2. 문을 여는 경우는 데크의 뒤에 넣는다.

🛠 나의 코드

---

from sys import stdin
from collections import deque
t = int(input())

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

def BFS(sx, sy):
    dist = [[-1]*(w+2) for _ in range(h+2)]
    q = deque()
    dist[sx][sy] = 0
    q.append((sx, sy))
    while q:
        tx, ty = q.popleft()
        for k in range(4):
            nx, ny = tx+dx[k], ty+dy[k]
            if nx < 0 or nx >= h+2 or ny < 0 or ny >= w+2:
                continue
            if arr[nx][ny] == '*' or dist[nx][ny] != -1:
                continue
            elif arr[nx][ny] == '#':
                dist[nx][ny] = dist[tx][ty] + 1
                q.append((nx, ny))
            else:
                dist[nx][ny] = dist[tx][ty]
                q.appendleft((nx, ny))
    return dist


for _ in range(t):
    h, w = map(int, input().split())
    arr = ['.'*(w+2)]
    for _ in range(h):
        arr.append('.'+stdin.readline().strip()+'.')
    arr.append('.'*(w+2))
    #  시작 위치 찾기
    start = []
    for i in range(h+2):
        for j in range(w+2):
            if arr[i][j] == '$':
                # arr[i][j] = '.'  # 예외를 만들지 않기 위해 '.'으로 바꿔주는 것 중요
                start.append((i, j))

    move_arr = []
    for x, y in start:
        move_arr.append(BFS(x, y))
    dz = BFS(0, 0)
    mn = 987654321
    for i in range(h+2):
        for j in range(w+2):
            if arr[i][j] == '*':
                continue
            sm = dz[i][j]
            for t in range(len(move_arr)):
                sm += move_arr[t][i][j]
            if arr[i][j] == '#':
                sm -= len(move_arr)
            mn = min(mn, sm)
    print(mn)

📝 정리

---

• .과 # 즉 문과 빈 공간이 모두 back으로 들어가면 먼저 문을 열고 지나간 자리는 문을 열지 않고 갈 수 있더라도 dist를 갱신할 수 없다.

1 방향에서 먼저 검사를 하면 문을 열고 난 후 $에 도달 하게 된다.
하지만 2방향에서 검사를 하면 문을 열지 않고 $에 도달할 수 있다.
따라서, 문을 가장 조금 여는 방향을 먼저 검사하도록 해야한다.

--	👇1	--
*	#	*	*
*	$	.	👈2
*	*	*	*

• 문을 여는 비용이 작은 것부터 먼저 탐색할 수 있도록 앞에 넣어준다.

🎈 참고

---

rebas님 블로그