문제
https://www.acmicpc.net/problem/16235
풀이
이 문제는 나무를 저장할 자료구조를 잘 선택해야합니다. 저는 결국 deque를 선택했고, 각 칸마다의 나무들을 각각 저장하는 deque를 만들었습니다. (100개의 deque) 나무들의 위치는 deque의 위치로 알 수 있으므로 나이만 저장하면 됩니다. 이때 나이순으로 정렬하는 것이 좋습니다. 오름차순인지 내림차순인지는 deque이므로 크게 중요하지 않습니다. 나이순으로 정렬해야 봄, 여름 처리시 빠르게 양분을 먹이고, 남은 죽은 나무들을 제거할 수 있습니다.
deque을 사용한 이유는, 앞 뒤에 저장 또는 삭제할 일이 많기 때문입니다. 나무가 번식할 때는 deque의 앞에 추가해야하고, 죽은 나무를 제거할 때는 deque의 뒤에서 pop하면서 빼야합니다.
알고리즘 흐름은 아래와 같습니다.
- 나무들을 입력받고 deque[r][c]에 나무를 추가한다.
- 모든 땅의 양분을 5로 초기화하고, 동시에 각 칸의 나무들을 나이별로 오름차순 정렬한다.
- 봄 & 여름 처리
- 가을 처리
- 겨울 처리
- 위의 3~5번 과정을 k회 반복하고, 마지막에는 각 칸의 나무들의 합계를 답으로 출력.
봄 & 여름 처리
각 칸의 나무들은 오름차순으로 정렬되어있습니다. 따라서 나무 deque의 앞에 있는 나무부터 순차적으로 양분을 먹입니다. 만약 특정 시점에 양분이 부족하다면, 그 나무부터 뒤에 있는 나무는 모두 죽었다고 생각할 수 있습니다.
이 땅에 10의 양분이 있다고 가정합시다. 그리고 아래는 그 땅에 있는 나무들의 나이 deque입니다.
| 1 | 1 | 2 | 3 | 3 | 4 | 6 | 7 | 8 | 9 |
앞의 나무 5개까지는 양분을 먹을 수 있지만, 나이가 4인 나무부터는 양분을 먹지 못합니다. 따라서 그 뒤의 나무도 모두 죽은 나무로 처리하면 됩니다.
죽은 나무들은 갯수를 파악해서, pop_back을 통해서 빼주면 됩니다.
가을 처리
단순하게 각 칸을 순회하면서 나이가 5의 배수인 나무에 대해서만 가을 처리(나무 번식)를 해줍니다. 번식할 나무는 주변 8칸에 나이가 1인 나무를 뿌립니다. 나이가 0인 나무는 존재하지 않으므로, 나이 1인 나무는 항상 가장 어린 나무가 됩니다. 따라서 나무 deque의 맨 앞에 넣어주면, 정렬을 유지하면서 나무를 추가할 수 있습니다. 만약 내림차순으로 정렬했다면 맨 뒤에 추가해야합니다.
겨울 처리
처음에 입력받은 A를 각 칸의 양분에 더해주면 됩니다.
고민할만한 부분
deque대신 vector 또는 list를 사용하면 안되나?
vector는 array로 구현된 리스트이므로 양 끝에 추가, 삭제시 O(N)이 소요됩니다. 추가 삭제가 빈번하게 발생하는데 O(N)은 느립니다.list의 경우에는 저도 아직 잘 모르겠습니다. 얼핏 봐서는 순회가 느린 것 같습니다. 직관적으로 생각하면 어차피 순회를 돌때 앞에서부터 링크를 타고 순회하므로 느릴 것 같지는 않은데… 측정해보니까 deque를 사용하면 300ms걸리던게 list를 사용하면 900ms정도가 걸리네요? 자세한 구현을 찾아봐야 알겠지만… 제 생각에는 부분 연속적으로 메모리상에 저장되는 deque와 달리 완전히 파편화되어 저장되는 list라서 순회하는데에 더 오래 걸리는걸까요?
하나의 deque에 모든 나무를 (x, y, age)형태로 저장하면 안되나?
이 방식의 문제점은 입력을 받는 족족 deque에 넣으므로, 순회를 돌 때도 순서대로 칸별로 나무들을 처리하는게 아니라 랜덤하게 나무들을 처리합니다. 물론 정렬된 형태로 넣을 수도 있지만, 입력이 많아지면 정렬에 시간이 많이 소모됩니다. 단순히 K=1000, M=100 이라고 가정해도 1000100log100 정도 입니다. 게다가 primitive type이 아닌 타입의 정렬은 시간이 더 오래걸립니다.
그리고 반드시 봄 처리가 끝나고 여름 처리를 해야합니다. 왜냐하면 특정 칸에 봄 처리가 아직 끝나지 않았는데 여름 처리(죽은 나무들을 땅에 양분으로 저장)를 하면, 땅에 양분 저장 후에 처리되는 나무들이 죽은 나무인지 판단할 수 없습니다. 이 문제때문에 죽은 나무들을 쉽게 삭제할 수 없습니다. pop_back을 사용해서 삭제할 수 없고, deque의 양 끝점이 아니라 중간 지점에서 여러번 remove 해야하므로 시간이 오래 걸립니다.
코드
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int n, m, k; // NxN, m개 나무, k년 후
int A[11][11];
int food[11][11];
deque<int> trees[11][11];
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
void next() {
// spring & summer
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int &foodAt = food[i][j];
int deadFrom = 0;
int foodAdd = 0;
for (auto &age: trees[i][j]) {
if (foodAt >= age) {
foodAt -= age++;
deadFrom++;
} else {
foodAdd += age / 2;
}
}
foodAt += foodAdd;
for (int x = trees[i][j].size() - 1; x >= deadFrom; x--) {
trees[i][j].pop_back();
}
}
}
// fall
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (auto &tree: trees[i][j]) {
if (tree % 5 == 0) {
for (int dir = 0; dir < 8; dir++) {
int nextR = i + dr[dir];
int nextC = j + dc[dir];
if (nextR < 0 || nextR >= n || nextC < 0 || nextC >= n) {
continue;
}
trees[nextR][nextC].push_front(1);
}
}
}
}
}
// winter
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
food[r][c] += A[r][c];
}
}
}
unsigned int solve() {
for (int i = 0; i < k; i++) {
next();
}
unsigned int result = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
result += trees[r][c].size();
}
}
return result;
}
int main() {
ios::sync_with_stdio(true);
cin.tie(nullptr);
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> A[i][j];
}
}
int r, c, age;
for (int i = 0; i < m; i++) {
cin >> r >> c >> age;
trees[r - 1][c - 1].push_back(age);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
food[i][j] = 5;
sort(trees[i][j].begin(), trees[i][j].end());
}
}
cout << solve() << '\n';
return 0;
}