📑 문제
문제링크 : 벽 부수고 이동하기 3
🤔 처음 생각
전형적인 BFS 문제라고 생각했습니다. 그래서 visited[N * M][2] 크기의 2차원 리스트를 만들어서 풀 수 있겠지 생각했습니다. 참고로 visited[N][M][2] 3차원 리스트로 하지 않은 이유는 차원을 낮추면 더 빠르지 않을까라는 생각이었습니다만, 이번처럼 N * M 이 큰 경우에는 더 느리더군요.
그런데 시간초과가 나오더라구요. 지금 생각해보면 3차원 리스트로 풀었으면 시간초과가 나지는 않았을 것 같지만, 그 당시에는 더 빠른 방법이 존재한다고 생각했고 다른 방법을 모색했습니다.
🎯 풀이방법
BFS 문제이며, 시간복잡도는 $O(N M)$ 입니다.
arr : 미로가 담긴 리스트. 각 요소에 행에 해당하는 문자열이 들어있다.
crack_count : 미로의 각 칸에 대응되는 리스트로, 각 칸에 도달했을 때의 부순 횟수를 저장
풀이방법의 핵심은 crack_count 에 있습니다. BFS 나 DP 에서 일반적으로 사용하는 visited 와는 다르게 해당 칸에 도착했을 때 부순 횟수를 저장합니다. 그리고 다음에 그 칸으로 오는 경우 저장한 부순 횟수보다 적게 부순 경우에만 큐에 넣어주어 BFS 를 진행합니다.
crack_count[N][M] 를 만들어 주고 모든 칸을 (K+1) 로 초기화시켜줍니다. (K+1) 로 초기화 시켜주는 이유는 최대 K 번까지 벽을 부술 수 있으므로, 특정 칸에 처음으로 K 번 벽을 부수고 도달했을 때 큐에 넣어줄 수 있음을 보장해주기 위해서입니다.
(0, 0) 위치에서부터 (N-1, M-1) 위치까지 상하좌우 움직여가며 BFS 를 진행합니다.
BFS 를 진행할 때, 다음 칸에 이전에 도착한 경우의 부순 횟수보다 적을 경우에만 탐색을 진행합니다.
다음 칸이 벽일 경우와 빈 칸일 경우, 각 경우에 따라 적절한 행동을 취합니다.
빈 칸일 경우, crack_count 에 현재 부순 횟수를 저장하고, 큐에 현재 상태를 추가합니다.
벽일 경우, (부순 횟수 + 1)이 해당 칸의 crack_count 보다 작을 경우에만 부수고 나아갈 수 있습니다. 현재가 낮이라면 부수고 나아간 후, crack_count 에 반영하고 큐에 추가해줍니다. 현재 상태를 큐에 추가하여 낮이되기를 기다립니다.
BFS 를 진행하며 마지막 칸에 도달한 경우에는 BFS 단계를 return 해줍니다. 도달하지 못하고 큐가 비게 된다면, 도달할 수 없으므로 -1 을 return 해줍니다.
🔎 유의할 점
벽을 만나지 않았다면 굳이 제자리에서 낮이 되기를 기다리지 않아도 됩니다. 실질적으로 낮이 필요한건 벽을 부술 때 뿐이니까요. 낮이 되길 기다리는건 오히려 탐색량을 늘릴 뿐입니다.
낮밤 여부는 따로 변수로 저장해도 되지만, BFS 단계가 홀수일 때는 낮, 짝수일 때는 밤으로 생각할 수 있습니다.
다음 칸으로 진행하기 전에 현재까지 부순 횟수와 해당 칸의 crack_count 와 비교하여 탐색량을 줄일 수 있습니다. 왜냐하면 이전 BFS 단계에서 탐색 순서에 따라 큐에 부순 횟수가 다른 같은 칸을 큐에 넣어줄 수 있습니다. 아래 예와 같은 경우 2번을 먼저 수행한 후 1번을 수행하면, 큐에 (1, 3) 칸이 두 번 들어갑니다. 하지만 실질적으로 BFS 를 수행해야하는 경우는 1번 경우이므로 코드의 31번 라인과 같이 비교하여 탐색량을 줄일 수 있습니다.
예제 입력 4에서 (0, 0) → (0, 1) → (0, 2) → (0, 3) → (1, 3) 순으로 진행하면 부순 횟수가 1번입니다.
(0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 3) 순으로 진행하면 부순 횟수가 2번입니다.
🧐 알게된 점
- 2 차원 문제에서 N * M 이 큰 경우, 1차원 리스트로 만들어 푸는 방식은 더 느리다.
💻 코드
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
59
60
61
62
63
from sys import stdin
from collections import deque
input = stdin.readline
def solve():
N, M, K = map(int, input().split())
if N == 1 and M == 1:
return 1
arr = [input()[:-1] for _ in range(N)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
crack_count = [[K + 1] * M for _ in range(N)]
crack_count[0][0] = 0
# (x, y, 벽 부순 횟수)
que = deque([(0, 0, 0)])
N_, M_ = N - 1, M - 1
ans = 1
while que:
l = len(que)
for _ in range(l):
ox, oy, crack = que.popleft()
if ox == N_ and oy == M_:
return ans
elif crack == crack_count[ox][oy]:
for dx, dy in d:
x = ox + dx
y = oy + dy
if 0 <= x < N and 0 <= y < M:
if crack < crack_count[x][y]:
# 다음 칸이 빈칸인 경우
# 낮이든 밤이든 상관없다
if arr[x][y] == '0':
crack_count[x][y] = crack
que.append((x, y, crack))
# 다음 칸이 벽인 경우
else:
if crack + 1 >= crack_count[x][y]:
continue
# 낮인 경우만 벽을 부술 수 있다
elif ans & 1:
crack_count[x][y] = crack + 1
que.append((x, y, crack + 1))
# 밤인 경우 제자리에 머무른다
else:
que.append((ox, oy, crack))
ans += 1
return -1
if __name__ == '__main__':
print(solve())
Comments powered by Disqus.