1️⃣ 서론
백준 문제 3055번 탈출 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
이 문제는 물이 차기 전에 안전하게 고슴도치가 비버의 굴로 이동하게 하는 가장 빠른 시간을 출력하는 문제입니다.
비어있는 곳은 ‘.’로 표시되어 있고, 물이 차있는 지역은 ‘*’, 돌은 ‘X’로 표시되어 있습니다.
비버의 굴은 ‘D’로, 고슴도치의 위치는 ‘S’로 나타내어져 있습니다.
물과 고슴도치는 돌을 통과할 수 없습니다.
또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없습니다.
3️⃣ 풀이
이 문제풀이의 핵심은 고슴도치와 물을 어떻게 동시에 이동시킬 것이냐 입니다.
이 문제는 물이 갈 수 있는 최단경로 배열로 먼저 물의 각 공간마다의 도착시간을 구한 후
해당 공간에 비버가 그 시간보다 짧은 시간 내에 도착할 수 있는 지를 알아내면 됩니다.
그렇게 두개의 공간을 bfs로 구하면 어렵지 않게 풀 수 있었습니다.
그럼 소스코드를 보시겠습니다.
4️⃣ 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import sys
from collections import deque
r, c = map(int, input().split())
arr = []
q = deque()
for _ in range(r):
arr.append(list(sys.stdin.readline().rstrip()))
waterMap = [[-1] * c for _ in range(r)]
beaverMap = [[-1] * c for _ in range(r)]
start = []
end = []
# 고슴도치의 위치를 start로 정하고 갈수 있는 '.' 표시로 바꿉니다.
for i in range(r):
for j in range(c):
if arr[i][j] == 'D':
end = [i, j]
elif arr[i][j] == 'S':
start = [i, j]
beaverMap[i][j] = 0
arr[i][j] = '.'
elif arr[i][j] == '*':
q.append([i, j])
waterMap[i][j] = 0
dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
# 물이 갈 수 있는 최단 경로를 먼저 waterMap 에 표시해줍니다.
while q:
x, y = q.popleft()
for i in range(4):
dx = x + dir[i][0]
dy = y + dir[i][1]
if 0 <= dx < r and 0 <= dy < c and arr[dx][dy] == '.' and waterMap[dx][dy] == -1:
waterMap[dx][dy] = waterMap[x][y] + 1
q.append([dx, dy])
# 고슴도치가 갈 수 있는 곳을 waterMap과 비교해 waterMap보다 작으면 갈 수 있게 해줍니다.
# 단, 동시에 물과 고슴도치가 도착하는 경우도 이동할 수 없으므로 +1로 비교해줍니다.
q.append(start)
while q:
x, y = q.popleft()
for i in range(4):
dx = x + dir[i][0]
dy = y + dir[i][1]
if 0 <= dx < r and 0 <= dy < c and arr[dx][dy] in '.D' and beaverMap[dx][dy] == -1:
if beaverMap[x][y] + 1 < waterMap[dx][dy] or waterMap[dx][dy] == -1:
beaverMap[dx][dy] = beaverMap[x][y] + 1
q.append([dx, dy])
# 고슴도치가 갈수 없는 경우 KAKTUS를 표시
if beaverMap[end[0]][end[1]] == -1:
print('KAKTUS')
else:
print(beaverMap[end[0]][end[1]])
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
