[ BOJ - 16235번 ] 나무 재테크 (C++)

https://www.acmicpc.net/problem/16235

 

 처음에 생각했던 풀이 방법은 다음과 같다.

 

1. 봄, 여름, 가을, 겨울 별로 기능 구현.

 

   봄: 나무의 나이와 양분의 양을 비교하여

       (나무 나이 < 양분)일 경우: 나무 나이++, 양분의 양 - 나무 나이

       (나무 나이 > 양분)일 경우: 나무가 죽고 양분의 양에는 변화 x

       위 기능을 칸에 있는 어린 나무부터 순서대로 수행

       (양분 배열을 ORIGIN, AUX로 나누어 저장, 나무는 좌표와 나이 변수를 갖는 구조체로 저장, 살아있는 나무와 죽은 나무 배열을 나누어 생성, 나무가 죽으면 살아있는 나무 배열에서 죽은 나무 배열로 이동)

 

   여름: (죽은 나무의 나이/2)를 양분 배열의 칸에 추가

        -> 죽은 나무 배열을 돌며 기능 수행하고 죽은 나무 배열을 초기화

 

   가을: 살아있는 나무 중 나이가 5의 배수인 나무들을 찾고, 각 나무의 인접한 8칸에 나이 1인 나무를 추가

        -> 살아있는 나무 배열을 돌며 나이 5인 나무를 찾고, 인접한 위치 좌표와 나이 1을 저장한 살아있는 나무를 배열에 추가

 

   겨울: 처음 입력된 양분만큼 땅에 양분 추가.

        -> ORIGIN 배열에 저장된 양분만큼 AUX 배열에 추가.

 

2. 연단위로 계절을 반복하며 위 기능을 수행하고, 지난 년수를 세주는 기능

   -> K번 반복한 뒤 살아있는 나무의 수를 세서 출력.

 

[ 발생한 문제 ]

1. 양분이 처음에 모든 칸에 5씩 들어있다는 조건을 문제를 이해할 때 놓치고 입력된 양분이 초기 조건이라 착각하고 구현했기 때문에, 디버깅에 시간을 오래 허비했다.

 

2. vector 순회 도중 erase 사용했기 때문에 size와 index가 순회 도중에 바뀌어 side effect 발생했다.

 

3. 2번을 해결하기 위해 Tree 구조체에 dead 멤버 변수 추가해 erase 대신 죽은 Tree 판단에 사용하였으나 시간 초과가 발생했다.

 

4. 3번을 해결하기 위해 deque에 저장해 순회, 삭제하도록 수정하였으나 "틀렸습니다"가 발생했다.

(문제와 질문하기에 있는 모든 테스트 케이스 통과해 끝까지 이유를 알아내지 못했으나, 순회 시 인덱스 오류일 것으로 예상되고 sort에 필요한 시간복잡도 때문에 결국 시간 초과 일어날 것으로 생각된다.)

 

 즉, container 순회에서 오류 일어나고, 정렬해야하는 container의 size가 크기 때문에 sort 반복 시 시간 초과가 발생했다.

 

[ 풀이 방법 ]

 처음 생각한 풀이 방법에서 시간 초과 문제를 해결하기 위해 구현 방법 중 일부를 다음과 같이 수정하였다.

 

 구조체 생성 시 걸리는 시간과 sort에 걸리는 시간을 줄이기 위해, 구조체로 Tree를 저장하는 대신 3차원 배열을 만들어 좌표를 index로  사용해 각 좌표에 살아있는 Tree의 나이를 저장해 사용하고, sort할 필요가 없는 죽은 Tree만 deque에 저장하는 방법으로 구현하여 문제를 해결할 수 있었다.

 

[ 회고 ]

 실제 코딩테스트였다면 기존의 풀이법으로는 결국 오류를 해결했더라도 시간 초과가 발생하게 되었을 것이고, 이미 디버깅에 시간을 너무 많이 사용했기 때문에 시간 안에 풀지 못하고 끝났을 것이다.

 

 문제의 조건(양분의 초기 조건 착각, 시간 제한 0.3초)과 C++ 문법의 시공간복잡도와 활용 방법(vector erase시 size와 index에 영향, deque 순회하는 동시에 deque에 원소 삽입, 삭제 시 발생할 수 있는 side effect)을 정확히 파악하지 못해 풀 수 없었던 문제였다.

 

 시간 제한이 빡빡한 문제에는 구조체 생성을 피하고 + 공간복잡도는 늘리고 시간복잡도를 줄이는 풀이 방법을 생각해야 한다는 것을 떠올릴 수 있었다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <deque>

using namespace std;

int N, M, K;
vector<vector<int>> origin;
vector<vector<int>> aux;

int dirX[8] = {-1, -1, 0, 1, 1, 1, 0 ,-1};
int dirY[8] = {0, 1, 1, 1, 0, -1, -1 ,-1};

vector<vector<vector<int>>> livingTree;
deque<pair<int, int>> deadTree;
deque<int> deadTreeAge;

int year = 0;

void spring() {
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            
            if(livingTree[i][j].size() == 0) continue;
            
            vector<int> t;
            sort(livingTree[i][j].begin(), livingTree[i][j].end());
            
            for (int k = 0; k < livingTree[i][j].size(); k++) {
                
                if (livingTree[i][j][k] <= aux[i][j]) {
                    aux[i][j] -= livingTree[i][j][k];
                    t.emplace_back(livingTree[i][j][k]+1);
                } else {
                    deadTree.emplace_back(i, j);
                    deadTreeAge.emplace_back(livingTree[i][j][k]);
                }
            }
            
            t.swap(livingTree[i][j]);
            t.clear();
        }
    }
}

void summer() {
    
    while (!deadTree.empty()) {
        int x = deadTree.front().first;
        int y = deadTree.front().second;
        aux[x][y] += deadTreeAge.front()/2;
        
        deadTree.pop_front();
        deadTreeAge.pop_front();
    }
}

void autumn() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            
            if(livingTree[i][j].size() == 0) continue;
            
            for (int k = 0; k < livingTree[i][j].size(); k++) {
                
                if(livingTree[i][j][k]%5) continue;
                
                for (int dir = 0; dir < 8; dir++) {
                    int nx = i + dirX[dir];
                    int ny = j + dirY[dir];
                    
                    if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                    
                    livingTree[nx][ny].emplace_back(1);
                }
            }
        }
    }
}

void winter() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            aux[i][j] += origin[i][j];
        }
    }
}

void solve() {
    
    while (year < K) {
        spring();
        summer();
        autumn();
        winter();
        year++;
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M >> K;
    origin.resize(N, vector<int>(N));
    aux.resize(N, vector<int>(N));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> origin[i][j];
            aux[i][j] = 5;
        }
    }
    
    livingTree.resize(N, vector<vector<int>>(N, vector<int>()));
    for (int i = 0; i < M; i++) {
        int x, y, age;
        cin >> x >> y >> age;
        livingTree[--x][--y].emplace_back(age);
    }
    
    solve();
    
    int res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            
            res += livingTree[i][j].size();
        }
    }
    cout << res << '\n';
    
    return 0;
}