### 문제 분석
-
적당한 전략을 세워놓지 않고 구현에 들어가서 중간중간에 조건을 끼워 맞추다 보니 코드도 더러워졌고 버그를 잡기도 힘들었다.
-
구현도 구현이지만 이 문제는 데이터를 저장할 자료구조를 선택하는 것이 중요했던 문제였던 것 같다.
내 구현
vector<pair<int,int> > Tree_cor;
// 나무가 1개 이상 있는 공간의 좌표
int Tree_info[12][12][1002];
// [x_좌표][y_좌표][나무의 나이] -> 각각의 나이의 살아있는 나무들의 갯수
int Soil[12][12];
// 현재 토양의 양분
int A[11][11];
// 뿌릴 양분
나는 위에 처럼 자료구조를 선택했다. 처음부터 이러한 자료구조를 선택하고 들어갔다기 보다는 구현을 하다보니 봄을 구현할때 ''나이가 어린 나무부터 양분을 먹는다. '' 라는 조건을 구현하려다 보니 나무를 계속 정렬하는 것 보다는 애초에 나이를 인덱스로 만들어서 구현을 하는 것이 좋겠다는 생각이 들었다.
하지만 이렇게 구현하는것이 엄청난 패착이었다. 문제를 좀 살펴보면 나이( K )는 1살부터 1000살까지이고 각 칸은 10 x 10 100개가 된다. 따라서 전체 칸의 나무들을 모두 확인하는데 걸리는 시간은 1000 x 100 = 100000이 된다. 봄 여름 가을은 모든 나무들을 탐색해야 하니까 1년이 지나는데 적어도 100000회의 반복이 필요하게 된다.
또한 이런식으로 구현을 하다보니 나이를 1살 증가시키는 과정도
for(int i = 999; i >= 1; i--){
Tree_info[x_cor][y_cor][i+1] = Tree_info[x_cor][y_cor][i];
}
Tree_info[x_cor][y_cor][1] = 0;다음과 같이 복잡해졌고 나이가 1살인 나무들은 0으로 초기화 시켜야 하는데 이런 과정도 빼먹어서 버그를 잡는데 시간이 너무 오래 걸렸다.
또한 시간 제한이 0.3으로 매우 타이트해서 나무가 있는 칸의 좌표만을 가지고 있다가 해당 칸에 대해서만 봄 여름 가을 알고리즘을 수행하는 식으로 작성하려 했으나 중복없이 나무가 있는 칸의 좌표를 유지하느라 또 코드가 매우 복잡해졌다. 10 x 10이기 때문에 어차피 100개 밖에 안되서 100개를 모두 확인을 해도 큰 상관은 없었을 것 같은데 말이다.
또한 문제 자체는 0-index가 아니라 1-index를 사용하고 있었는데 바보같이 1-index로 된 값을 그대로 사용해서 0-index의 좌표로 사용해 버렸다. 이런 실수는 한번도 한적이 없는데 찾는데 제법 애를 먹었다. 인덱스는 항상 주의해야 하는 것 같다.
여차저차 구현을 하고 다른 사람들의 코드를 봤다. 그러던중 아주 아름다운 코드를 발견했다.( 해당 코드는 하단의 참조에 링크를 걸어 놓았다. ) 내 코드와는 아주 상이했다.
int N,M,K;
int Soil[12][12];
int A[12][12];
deque<int> Trees[12][12];
vector<int> DeadTrees[12][12];
해당 코드는 다음과 같은 2가지 이유로 덱을 사용했다.
-
덱을 사용해서 나무들을 저장하기 때문에 봄 부분에서 각각의 나무 자체를 나이가 어린 순서대로 접근 할 수 있다. 정렬이 따로 필요가 없다. 애초에 정렬을 한 상태로 가지고 있기 때문이다.
-
또한 가을의 번식 부분에서 나이가 1인 나무들을 추가하고자 할 때 deque의 앞 부분에 해당 나무를 바로 넣어줄 수 있다.
위와 같은 자료구조를 사용하니 코드가 훨씬 간결해졌고 구현도 훨씬 쉬워졌다. **적절한 자료구조의 선택이 얼마나 중요한지 깨달았다.
문제를 풀 때 항상 전략은 대략적으로 세우고 바로 구현에 들어갔는데 이번 문제를 통해서 전략을 세우고 자료를 어떠한 형태로 저장할지 선택하는 것이 추후 문제를 풀이 하는데에도 많은 영향을 미친다는 것을 깨달았다.
앞으로 문제를 풀이 할 때에는 무조건 빨리 풀이에 들어가기 보다는 내가 사용하고자 하는 자료구조가 타당한지 어느 정도 검증을 마친 상태로 들어가는 것이 시간을 단축하는 길인 것 같다.
얻은 것
1. 반복과 재귀의 복습
2. Modulo의 활용
전체 코드 [ 내 코드 - bad ]
#include <vector>
#include <iostream>
using namespace std;
vector<pair<int,int> > Tree_cor;
// 나무가 1개 이상 있는 공간의 좌표
int Tree_info[12][12][1002];
// [x_좌표][y_좌표][나무의 나이] -> 각각의 나이의 살아있는 나무들의 갯수
int Soil[12][12];
// 현재 토양의 양분
int A[11][11];
// 뿌릴 양분
void init(){
ios::sync_with_stdio(0);
cin.tie(0);
}
int N,M,K;
void get_input(){
cin >> N >> M >> K;
for(int i = 0 ; i < N; i++){
for(int j = 0 ; j < N; j++){
Soil[i][j] = 5;
cin >> A[i][j];
}
}
for(int i = 0 ; i < M; i++){
int x_cor;
int y_cor;
int age;
cin >> x_cor >> y_cor >> age;
Tree_cor.push_back(make_pair(x_cor - 1, y_cor - 1));
Tree_info[x_cor - 1][y_cor - 1][age]++;
}
}
void print_tree_state(){
cout << "try" << "\n";
for(int i = 0 ; i < Tree_cor.size(); i++){
int x_cor = Tree_cor[i].first;
int y_cor = Tree_cor[i].second;
cout << "x : " << x_cor << " y : " << y_cor << "\n";
for(int age = 0 ; age < 1001; age++){
if(Tree_info[x_cor][y_cor][age] > 0){
cout << "age : " << age << " count : " << Tree_info[x_cor][y_cor][age] << "\n";
}
}
}
}
void print_soil(){
for(int i = 0 ; i < N; i++){
for(int j =0 ; j < N; j++){
cout << Soil[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
}
void spring_and_summer(){
int marker[12][12];
for(int i = 0 ; i < N; i++){
for(int j = 0 ; j < N; j++){
marker[i][j] = 0;
}
}
for(int i = 0 ; i < Tree_cor.size(); i++){
marker[Tree_cor[i].first][Tree_cor[i].second] = 1;
} // 기존에 있던 나무들을 1로 마킹
for(int i = 0 ; i < Tree_cor.size(); i++){
int e = 0;
int x_cor = Tree_cor[i].first;
int y_cor = Tree_cor[i].second;
// 각각의 셀에 대하여
int tree_cnt_per_cell = 0;
for(int age = 0 ; age < 1001; age++){
// 각각의 나이 별로
int tree_cnt = Tree_info[x_cor][y_cor][age];
for(int j = 0 ; j < tree_cnt ; j++){
if(Soil[x_cor][y_cor] >= age){
Soil[x_cor][y_cor] -= age;
}else{
// cout << "here\n";
Tree_info[x_cor][y_cor][age] -= 1;
e += age/2;
}
}
tree_cnt_per_cell += Tree_info[x_cor][y_cor][age];
}
if(tree_cnt_per_cell == 0){
marker[x_cor][y_cor] = 0;
}
Soil[x_cor][y_cor] += e;
for(int i = 999; i >= 1; i--){
Tree_info[x_cor][y_cor][i+1] = Tree_info[x_cor][y_cor][i];
}
Tree_info[x_cor][y_cor][1] = 0;
}
Tree_cor.clear();
for(int i = 0 ; i < N; i++){
for(int j = 0 ; j < N; j++){
if(marker[i][j] == 1) {
Tree_cor.push_back(make_pair(i,j));
}
}
}
}
int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};
void fall(){
int marker[12][12];
for(int i = 0 ; i < N; i++){
for(int j = 0 ; j < N; j++){
marker[i][j] = 0;
}
}
for(int i = 0 ; i < Tree_cor.size(); i++){
marker[Tree_cor[i].first][Tree_cor[i].second] = 1;
}// 기존에 있던 좌표들
for(int i = 0 ; i < Tree_cor.size(); i++){
int x_cor = Tree_cor[i].first;
int y_cor = Tree_cor[i].second;
for(int age = 0 ; age < 1001; age++){
if(age % 5 != 0) continue;
int tree_cnt = Tree_info[x_cor][y_cor][age];
for(int j = 0 ; j < tree_cnt ; j++){
for(int d = 0; d < 8; d++){
int nx = x_cor + dx[d];
int ny = y_cor + dy[d];
if(nx >= N || ny >= N || ny < 0 || nx < 0) continue;
Tree_info[nx][ny][1]++;
marker[nx][ny] = 1; // 새로 생긴 좌표들
}
}
}
}
Tree_cor.clear();
for(int i = 0 ; i < N; i++){
for(int j = 0 ; j < N; j++){
if(marker[i][j] == 1) {
Tree_cor.push_back(make_pair(i,j));
}
}
}
}
void winter(){
for(int i = 0 ; i < N; i++){
for(int j= 0 ; j < N; j++){
Soil[i][j] += A[i][j];
}
}
}
int main(void){
init();
get_input(); // clear
for(int i = 0 ; i < K; i++){
spring_and_summer();
fall();
winter();
// print_tree_state();
// print_soil();
}
int ans = 0;
for(int i = 0 ; i < Tree_cor.size(); i++){
int x = Tree_cor[i].first;
int y = Tree_cor[i].second;
for(int i = 0 ; i < 1001; i++){
ans += Tree_info[x][y][i];
}
}
// cout << Tree_cor.size() << "\n";
cout << ans << "\n";
return 0;
}참조
deque을 이용한 코드
