백준 9376번: 탈옥 (python)
by VICENTE97P4
Dec. 19, 2021, 5:26 p.m.
문제 링크: https://www.acmicpc.net/problem/9376
굉장히 고민을 많이 했고, 그럼에도 풀지 못하고 정답을 봤고,
그럼에도 이해하지 못해서 한참을 또 고민했던 문제입니다.
제 생각에는 이 문제에 대해 해답을 올려놓은 분들은 많은데, 코드와 이유에 대해서 설명이 부실하다고 생각합니다.
그래서 제가 이해한 바를 써보려고 합니다.
개인적으로 정말 어렵고 좋은 문제라고 생각하고,
이게 어떻게 플래티넘 5인지 아직도 이해할 수 없습니다.
잘하는 사람들이.. 자기들이 쉽게 풀었다고 난이도를 낮게 준 것 같은데..
저같은 초보는 얼마나 버거운데.. 너무하다는 생각이 듭니다.
개인적으로 정말 경악을 금치 못하는 부분이 3군데나 있는 초고난도 문제였다고 생각합니다.
일단 코드를 보겠습니다.
import sys
from collections import deque
input = sys.stdin.readline
d = [[-1, 0], [0, -1], [1, 0], [0, 1]]
T = int(input().strip())
def BFS(y, x):
q = deque()
cnt = [[-1] * (w + 2) for _ in range(h + 2)]
q.append([y, x])
cnt[y][x] = 0
while q:
y, x = q.popleft()
for dy, dx in d:
ty = y + dy
tx = x + dx
if 0 <= ty < h + 2 and 0 <= tx < w + 2:
if cnt[ty][tx] == -1:
if prison[ty][tx] == '.':
q.appendleft([ty, tx])
cnt[ty][tx] = cnt[y][x]
elif prison[ty][tx] == '#':
q.append([ty, tx])
cnt[ty][tx] = cnt[y][x] + 1
return cnt
for _ in range(T):
h, w = map(int, input().split())
prison = [['.'] * (w + 2)]
for i in range(h):
prison.append(list('.' + input().strip() + '.'))
prison.append(['.'] * (w + 2))
start = []
for i in range(1, h + 1):
for j in range(1, w + 1):
if prison[i][j] == '$':
start.append([i, j])
prison[i][j] = '.'
cnt1 = BFS(start[0][0], start[0][1])
cnt2 = BFS(start[1][0], start[1][1])
cnt3 = BFS(0, 0)
ans = float('inf')
for i in range(1, h + 1):
for j in range(1, w + 1):
if cnt1[i][j] != -1 and cnt2[i][j] != -1 and cnt3[i][j] != -1:
if prison[i][j] == '.':
ans = min(ans, cnt1[i][j] + cnt2[i][j] + cnt3[i][j])
elif prison[i][j] == '#':
ans = min(ans, cnt1[i][j] + cnt2[i][j] + cnt3[i][j] - 2)
print(ans)
큰 컨셉은 각 죄수가 도달하는 칸에 최소한으로 연 감옥 수를 저장하고, 이를 모두 더하고,
더한 값 중 벽이 아닌 가장 값이 작은 칸을 정답으로 제출할겁니다.
무슨 말인지 하나도 모르겠지만 차근차근 생각해봅시다.
첫 번째로 충격을 받았던 부분은 감옥 밖의 장소를 1줄씩 추가해야 한다는 점입니다.
def BFS(y, x):
q = deque()
cnt = [[-1] * (w + 2) for _ in range(h + 2)]
q.append([y, x])
알고리즘 문제풀이가 서툴기도 했지만, 강제로 맵을 상하좌우로 1줄씩 늘린다는 생각 자체를 하지 못했습니다.
이는 어떤 경우 때문에 그렇냐면 두 죄수가 벽에 막혀서 아예 만나지 못하는 경우가 있기 때문입니다.
*****
#$*$#
*****이 경우, 칸을 상하좌우에 1줄씩 새로 추가시켜 주지 않는다면 문을 연 최소 횟수를 파악하기 굉장히 힘듭니다.
물론 위 그림만 놓고 보면 다른 방법으로 파악할 수 있지만 BFS를 일관되게 적용하기 힘들고,
이런 경우가 복잡하게 꼬여서 주어진다면 정말 파악하기 힘들어지죠.
방 안팎을 자유롭게 다녀야 할 경우는 칸을 상하좌우로 강제로 1줄씩 추가시켜주는 테크닉이 유용하다는 것을 배웠습니다.
자, 그럼 그렇게 상하좌우로 강제로 늘렸다고 합시다.
그럼 어떻게 최소한의 감옥 문을 열고 돌아다니게 구현할까요?
여기서 0-1 BFS가 사용됩니다.
cnt[y][x] = 0
while q:
y, x = q.popleft()
for dy, dx in d:
ty = y + dy
tx = x + dx
if 0 <= ty < h + 2 and 0 <= tx < w + 2:
if cnt[ty][tx] == -1:
if prison[ty][tx] == '.':
q.appendleft([ty, tx])
cnt[ty][tx] = cnt[y][x]
elif prison[ty][tx] == '#':
q.append([ty, tx])
cnt[ty][tx] = cnt[y][x] + 1
return cnt
특히
if 0 <= ty < h + 2 and 0 <= tx < w + 2:
if cnt[ty][tx] == -1:
if prison[ty][tx] == '.':
q.appendleft([ty, tx])
cnt[ty][tx] = cnt[y][x]
이 부분이 중요합니다.
새로 전진한 칸이 .(길)이면 #(벽)을 만나기 전까지 우선적으로 돌아다니도록 q의 왼쪽에 추가해주는 겁니다.(appendleft)
구현은 아무것도 아닌데 모르고 있었다면 떠올리기 힘든 테크닉이죠.
이렇게 한 칸 한 칸 다니면서 각 칸마다 최소로 문을 열고 도착한 횟수를 cnt에 기록합니다.
그럼 정답은 어떻게 구할까요?
각 죄수가 최소로 문을 열고 돌아다닌 칸에 기록해둔 문을 연 횟수를 다 더합니다.
그리고 모든 칸을 살펴보며 그 중 가작 작은 값이 정답입니다.
cnt1 = BFS(start[0][0], start[0][1])
cnt2 = BFS(start[1][0], start[1][1])
cnt3 = BFS(0, 0)
ans = float('inf')
for i in range(1, h + 1):
for j in range(1, w + 1):
if cnt1[i][j] != -1 and cnt2[i][j] != -1 and cnt3[i][j] != -1:
if prison[i][j] == '.':
ans = min(ans, cnt1[i][j] + cnt2[i][j] + cnt3[i][j])
elif prison[i][j] == '#':
ans = min(ans, cnt1[i][j] + cnt2[i][j] + cnt3[i][j] - 2)
print(ans)
이 부분인데요, 왜 각 죄수가 돌아다닌 칸을 더한 값 중 가장 작은 값이 정답이 되는 걸까요?
이런 식이면 한 죄수가 이미 문을 안 열고 지나온 길에는 0이 적혀있을 텐데 정답이 온전히 안 나오지 않을까요?
잘 생각해보면 이미 한 죄수가 지나온 그 길은 다른 한 죄수가 돌아다니면서 도달할 것이고 값을 채워줄 것입니다.
****#****
*..#.#..*
****#****
*$#...#$*
*********빨간 애가 지나온 길은 어차피
****#****
*..#.#..*
****#****
*$#...#$*
*********파란 애가 문을 열고 돌아다니면서 채워줄 것이라는 거죠.
그런데 이런 방식이면 한 가지 커버할 수 없는 경우가 생깁니다.
아까 보여드린 예에서 빨강이와 파랑이가 있던 자리에는 cnt가 얼마가 찍힐까요?
2가 찍히게 될겁니다.. 왜냐하면 BFS는 최단거리로 달리기 때문이죠.
그런데 정답은 3입니다..
이는 둘 사이의 최단거리를 벗어나는 곳에 있는 문은 포함시켜주지 않았기 때문입니다.
****#**** *..#.#..* ****#**** *$#...#$* *********
이를테면 위 초록색 문을 연 횟수는 빨강이와 파랑이가 있던 자리에는 기록되지 않겠죠.
해결책이 필요합니다.
이 문제를 구글링해보면 뜬금없이 제 3자(상근이)가 감옥 밖에서 구하러 오는 경우를 생각해서
(0, 0)에서 상근이가 구하는 경우까지 세어주고 최종 cnt에 더해줍니다.
그런데 받아들이는 입장에서는 갑자기 제 3자가 구하는 경우가 왜 나오는지, 왜 포함시켜야 하는지 이해하기 힘듭니다.
(최소한 저는 그랬습니다.)
아니 어차피 두 죄수가 최소한으로 문을 열면서 돌아다닐 건데, 갑자기 제 3자가 나오는 경우는 도대체 왜 생각하는 건지..
이에 대한 설명은 부실한 경우가 많습니다.
개인적으로 제 3자가 구해주러 오는 경우라고 표현하는 것은 오히려 받아들이는 데에 혼란만 준다고 생각합니다.
그 표현 보단 두 죄수의 각각의 움직임 만으로는 모든 칸에 포함할 수 없는 문을 포함해주기 위함이라고 생각하는게 편해 보입니다.
(꼭 (0,0)일 필요는 없습니다. 어떤 칸이든 감옥 밖이면 됩니다.)
우리는 정답을 구할 때 죄수가 방문했던 모든 칸들 중 문을 연 횟수가 가장 적은 값을 정답으로 제출할겁니다.
그러기 위해서는 모든 칸에 최소한으로 문을 연 횟수가 기록되어야 합니다.
이를 구현하기 위해 감옥 밖인 (0, 0)에서 BFS를 한 번 더 해주어서 두 죄수가 먼저 지나가서 이후에 열어야 했던 문(초록색)을
모두 추가해줍니다.
그래서 죄수는 2명인데 (0, 0)에서 출발하는 BFS가 하나 추가된 것입니다.
다른 설명에서는 이 감옥 밖 BFS를 상근이가 죄수들을 구하러 들어오는 경우로 표현한 것 같습니다.
cnt1 = BFS(start[0][0], start[0][1])
cnt2 = BFS(start[1][0], start[1][1])
cnt3 = BFS(0, 0)
추가적으로, 답을 구할 때, 문이 있던 칸은 -2를 해줘야 합니다.
ans = float('inf')
for i in range(1, h + 1):
for j in range(1, w + 1):
if cnt1[i][j] != -1 and cnt2[i][j] != -1 and cnt3[i][j] != -1:
if prison[i][j] == '.':
ans = min(ans, cnt1[i][j] + cnt2[i][j] + cnt3[i][j])
elif prison[i][j] == '#':
ans = min(ans, cnt1[i][j] + cnt2[i][j] + cnt3[i][j] - 2)
print(ans)
왜냐하면 문은 사실 1번만 열면 다시 닫히지 않는데, 3번의 BFS를 한 결과를 모두 더하면 +1이 아닌 +3이 되기 때문입니다.
정답으로 뽑힌 최소값이 기록된 칸이 갖는 의미는 3번의 BFS를 하던 도중 만난 칸입니다.
즉, 상근이, 빨강 죄수, 파랑 죄수가 돌아다니다가 만난 최소한으로 문을 연 칸이고,
(상근이는 가상 인물이니까, 사실 빨강죄수와 파랑 죄수가 만난 칸이죠.)
이후로 가상 인물인 상근이가 지나온 길은 사실 빨강 죄수와 파랑 죄수가 만나 함께 다닌 길이 됩니다.
예제에서는
****#****
*..#.#..*
****#****
*$#...#$*
*********보라색이 두 죄수가 만나는 칸(구현 상으로는 상근+빨강 죄수+파랑 죄수),
노란 칸이 두 죄수가 만나 함께 지나가는 길(상근이가 지나온 길)이 되겠네요.
긴 포스팅이었네요.
저는 위에서 진하게 처리한 3가지
1. 강제로 맵을 상하좌우 한 줄씩 늘린다.
2. 정답은 BFS 3번 값을 더한 값 중 최소값으로 구할거다
3. 감옥 밖에서 한 번 더 BFS를 해줘야 한다.
이 3가지가 매우 경악스러웠습니다.
이걸 어떻게 알아.. 어떻게 생각해내.. 이게 왜 플래5야..
그래도 정말 많은 테크닉과 개념을 배운 문제였습니다.
아직 갈 길이 멀고, 많이 배워야 함을 느낍니다.
1 view 1654
1빠
Updated: Dec. 19, 2021, 5:39 p.m.