📑 문제
문제링크 : Gaaaaaaaaaarden
🤔 생각의 흐름
풀기 위해 아이디어적 어려움을 느낄만한 부분은 크게 없는 것 같습니다. 배양액을 뿌릴 수 있는 위치들 중에서 서로다른 R 개와 G 개를 뽑아 BFS 를 수행해야합니다.
다만 좀 귀찮은 부분은 빨간색과 초록색 배양액의 BFS 를 병렬적으로 수행해야하는 부분입니다. 처음에는 visited 리스트에 방문한 위치를 boolean 으로 기록하고 각 배양액이 동시에 도달한 위치를 set 을 이용한 큐로 풀었습니다만 풀이가 많이 느렸습니다.
다른 분의 코드를 참고하여 입력받은 정원에 기록하는 방법을 알게되었습니다. 빨간색 배양액이 퍼질 자리에 +(현재 BFS 단계)를 기록하고 초록색 배양액이 퍼질 자리에는 -(현재 BFS 단계)를 기록합니다. 만약 초록색 배양액이 퍼질 자리에 현재 BFS 단계와 같은 수가 기록되어 있다면 동일한 단계에 퍼진 것이므로 꽃의 수를 +1 해주는 방식으로 빠르게 풀 수 있었습니다.
🎯 풀이방법
Brute Force, BFS, 구현 문제이며, 시간복잡도는 $O(2^{R+G} N M)$ 입니다.
arr : 1차원 리스트로 입력받은 정원
spot : 배양액이 뿌려질 수 있는 위치
r_spot, g_spot : BFS 를 수행하기 위한 큐
step : BFS 의 단계 (2부터 시작)
정원을 입력받아 배양액이 뿌려질 수 있는 위치를 모두 알아내고, 그 위치들의 값을 2에서 1로 바꾸어줍니다. (BFS 를 수행할 때 1인 칸으로만 배양액이 퍼질 수 있도록 하기 위해서입니다.)
재귀함수나 itertools 의 combinations 를 이용하여 배양액이 뿌려질 위치에서 R 개와 G 개를 뽑아 각 큐에 넣어줍니다. (제 코드에서는 combinations 를 이용하였습니다.)
BFS 수행을 위한 정원을 입력받은 정원을 복사하여 만듭니다.
빨간색 배양액이 있는 자리에서 현재 칸이 0 이상이라면(초록 배양액이 퍼진 자리는 음수로 기록되기 때문에) 상하좌우 인접한 칸의 값이 1인 곳(다른 배양액이 도달하지 않은 자리)으로 퍼져나가며, 퍼진 칸에는 +(현재 BFS 단계)를 기록합니다. 그리고 퍼진 칸을 큐에 넣어줍니다.
- 초록색 배양액이 있는 자리에서 상하좌우 인접한 칸의 값이 1인 곳 또는 현재 BFS 단계와 같은 값인 곳으로 퍼져 나갑니다.
- 값이 1인 칸으로 퍼진 경우 해당 칸에 -(현재 BFS 단계)를 기록하며 큐에 넣어줍니다.
- 값이 현재 BFS 단계와 동일한 칸으로 퍼진 경우 현재 BFS 의 꽃의 수를 +1 해주고, 해당 칸에 -(현재 BFS 단계)를 기록해줍니다.
- 초록색과 빨간색 배양액이 모두 큐에 남아 있는동안 BFS 를 계속 수행합니다. 가능한 모든 조합에 대해 BFS 를 수행하여 가장 많은 꽃이 핀 경우의 값을 return 해줍니다.
🔎 유의할 점
배양액을 뿌릴 수 있는 자리를 모두 알아낸 후 1로 바꾸어주거나, step 을 3부터 시작하고 배양액이 퍼질 자리의 값이 1 또는 2인지 확인해주어야 합니다. 저의 코드는 전자로 구현했습니다.
새로운 BFS 를 수행할 때마다 초기에 입력받은 정원을 그대로 사용하는 것이 아닌, 복사 후 사용해주어야 합니다.
💻 코드
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from sys import stdin
from itertools import combinations
input = stdin.readline
def solve():
N, M, G, R = map(int, input().split())
_len = N * M
arr = [0] * _len
idx = 0
for i in range(N):
arr[idx:idx+M] = [*map(int, input().split())]
idx += M
spot = [x for x, y in enumerate(arr) if y == 2]
for pos in spot:
arr[pos] = 1
ans = 0
for _spot in combinations(spot, G + R):
_spot = set(_spot)
for r_spot in combinations(_spot, R):
r_spot = [*r_spot]
g_spot = list(_spot - set(r_spot))
_arr = [*arr]
for r in r_spot:
_arr[r] = 0
for g in g_spot:
_arr[g] = 0
ans_val = 0
step = 2
while g_spot and r_spot:
if g_spot:
new_g_spot = []
for g in g_spot:
if 0 <= _arr[g]:
x, y = g // M, g % M
adj = [g - M if 0 < x else -1,
g + M if x < N - 1 else -1,
g - 1 if 0 < y else -1,
g + 1 if y < M - 1 else -1,
]
for nxt in adj:
if nxt != -1:
if _arr[nxt] == 1:
new_g_spot.append(nxt)
_arr[nxt] = step
g_spot = new_g_spot
if r_spot:
new_r_spot = []
for r in r_spot:
x, y = r // M, r % M
adj = [r - M if 0 < x else -1,
r + M if x < N - 1 else -1,
r - 1 if 0 < y else -1,
r + 1 if y < M - 1 else -1,
]
for nxt in adj:
if nxt != -1:
if _arr[nxt] == step:
ans_val += 1
_arr[nxt] = -step
elif _arr[nxt] == 1:
_arr[nxt] = -step
new_r_spot.append(nxt)
r_spot = new_r_spot
step += 1
if ans < ans_val:
ans = ans_val
return ans
if __name__ == '__main__':
print(solve())
Comments powered by Disqus.