[BOJ]2665. 미로만들기
❌code1
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
n = int(input()) # 정사각형 맵의 크기
MAP = [list(map(int, input())) for _ in range(n)] # 맵
min_cost_map = [[0] * n for _ in range(n)] # 최소 비용 저장 맵
min_cost_map[0][0] = 1 # 시작방의 최소 비용을 1로 설정
di = [-1, 1, 0, 0] # 상하좌우
dj = [0, 0, -1, 1] # 상하좌우
Q = [(0, 0)] # 큐 생성
while len(Q) > 0: # BFS
now = Q.pop(0)
now_r, now_c = now[0], now[1] # 현재 방의 행과 열
for k in range(4):
# 다음에 갈 수 있는 방은 맵을 벗어나지 않고 최소 비용이 계산되지 않은 방
nr, nc = now_r + di[k], now_c + dj[k]
if nr < 0 or nc < 0 or n <= nr or n <= nc:
continue
if min_cost_map[nr][nc] > 0:
continue
min_cost = n * n # (nr, nc) 방이 가질 수 있는 최소 비용
for check in range(4):
# (nr, nc) 방의 상하좌우를 다시 돌면서 0보다 큰 최소 비용을 구함
nr_check, nc_check = nr + di[check], nc + dj[check]
if nr_check < 0 or nc_check < 0 or n <= nr_check or n <= nc_check:
continue
if 0 < min_cost_map[nr_check][nc_check] < min_cost:
min_cost = min_cost_map[nr_check][nc_check]
# 최소 비용 할당
min_cost_map[nr][nc] = min_cost
if MAP[nr][nc] == 0: # 만약 이 방이 벽이었다면 비용 1 추가
min_cost_map[nr][nc] += 1
Q += [(nr, nc)] # 큐에 방 추가
print(min_cost_map[n-1][n-1] - 1)
시도
- BFS를 이용하여 방에 도달할 수 있는 최소 비용을 계산한다.
- 벽을 만나면 비용을
1씩 추가한다.
문제
큐에 순서대로 방을 추가하면 (nr, nc) 방의 상하좌우를 검사할 때에 더 적은 비용의 방이 미래에 들어올 수 있지만 이를 놓칠 수 있게 된다. 아래 그림에서 붉은 방의 경우가 그러하다. 예를 들어 (3,3)으로 표시된 방의 경우 아래에 비용이 1인 (4, 3) 방이 들어올 수 있지만, 이 방은 큐에서 (3, 3)보다 뒤에 들어오기 때문에 (3, 3) 방을 검사할 때에는 (4, 3) 방의 비용이 아직 존재하지 않는다.
⭕code2
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
n = int(input()) # 정사각형 맵의 크기
MAP = [list(map(int, input())) for _ in range(n)] # 맵
min_cost_map = [[0] * n for _ in range(n)] # 최소 비용 저장 맵
min_cost_map[0][0] = 1 # 시작방의 최소 비용을 1로 설정
di = [-1, 1, 0, 0] # 상하좌우
dj = [0, 0, -1, 1] # 상하좌우
Q = [(0, 0)] # 덱 생성
while len(Q) > 0: # BFS
now = Q.pop(0)
now_r, now_c = now[0], now[1] # 현재 방의 행과 열
for k in range(4):
# 다음에 갈 수 있는 방은 맵을 벗어나지 않고 최소 비용이 계산되지 않은 방
nr, nc = now_r + di[k], now_c + dj[k]
if nr < 0 or nc < 0 or n <= nr or n <= nc:
continue
if min_cost_map[nr][nc] > 0:
continue
# 다음 방에 현재 방의 비용을 할당
min_cost_map[nr][nc] = min_cost_map[now_r][now_c]
# 만약 벽이었다면 비용이 1 증가하고 덱의 오른쪽에 방을 추가
if MAP[nr][nc] == 0:
min_cost_map[nr][nc] += 1
Q += [(nr, nc)]
else: # 벽이 아니었다면 덱의 왼쪽에 방을 추가
Q = [(nr, nc)] + Q
print(min_cost_map[n-1][n-1] - 1)
시도
(nr, nc)가 벽이라면 리스트의 우측에 추가하고, 방이라면 리스트의 좌측에 추가한다. 이를 통해 벽을 뚫기 전에 도달할 수 있는 모든 방을 먼저 검사할 수 있게 된다.- 또한
(nr, nc)방의 상하좌우를 검사하여 최소비용을 다시 계산하는 과정을 하지 않을 수 있다.
요약
BFS에서 탐색 중간에 비용이 바뀌는 경우가 있을 때 탐색할 좌표를 큐의 왼쪽 또는 오른쪽으로 유동적으로 추가하여 답을 구할 수 있었다. 이 경우 정확히는 큐가 아니라 덱(double-ended queue)을 사용한 것이 된다. 큐에서 원소는 한쪽 끝에서 들어와 다른 쪽 끝에서 나가야 하지만 덱은 양방향 끝을 모두 이용할 수 있기 때문이다.
This post is licensed under CC BY 4.0 by the author.