[Algorithm] 백준 16235번 나무 재테크

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

문제 자체에는 어려움이 없음.

하지만, vector의 시간 복잡도에 대해서 이해가 부족하여 오래 잡았음.

앞으로 vector를 사용할 때는 sort 외에는 별도로 이용하지 않아야 겠다!!

문제 풀이 및 이슈 정리

1. (x, y) 가 있을 때, x를 행의 위치 그리고 y를 열의 위치로 하였음.

   → 백준 사이트 내 이슈를 확인하니, 행과 열이 헷갈린다는 말이 있으나 문제를 제대로 보면 그럴 리 없음.

2. 죽은 나무들을 vector erase로 처리하려고 하면, erase의 시간 복잡도가 O(N)이기 때문에 time out 발생함.

   → 이를 해결하기 위해 봄과 여름을 합치고 가을부터 살아남은 나무로 구성된 vector array를 사용하여 진행함.

3. 애초에 vector erase를 사용하게 되면, 하나씩 지울때마다 배열 내 위치와 전체 크기가 수정됨. 

   → 시간 복잡도가 심각하기 때문에 굳이 돌아가지 말고, 앞으로도 별도 배열로 추후에 처리하는 것이 좋을듯.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std;
 
struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {}
    Point(int x, int y) : x(x), y(y) {}
};
 
vector < vector < int > > ground;
vector < vector < int > > s2d2;
vector < pair < Point, int > > tree;
 
bool compPoint(const pair < Point, int > &a, const pair < Point, int > &b) {
    if (a.second < b.second) return true;
    return false;
}
int main()
{
    // N : A 배열의 값
    // M : 나무의 개수
    // K : K 년
    int N, M, K;
    cin >> N >> M >> K;
    ground.assign(N, vector<int>(N, 5));
    s2d2.assign(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> s2d2[i][j];
        }
    }
    int tx, ty, tv;
    for (int i = 0; i < M; i++) {
        cin >> tx >> ty >> tv;
        tree.push_back(make_pair(Point(tx - 1, ty - 1), tv));
    }
 
    // 1 YEAR
    // 봄 : 나무가 자신의 나이만큼 양분 먹고, 나이 + 1
    //      어린 나무 부터 먹고, 못 먹으면 죽음.
    // 여름 : 봄에 죽은 나무가 양분으로 변하게 됨. 
    //        나이 / 2 만큼 양분이 쌓임. (소수점 버림)
    // 가을 : 나이가 5의 배수인 나무가 8방향으로 번식함.
    // 겨울 : s2d2가 양분을 뿌림.
 
    int dx[8] = { -1,-1,-1,0,1,1,1,0 };
    int dy[8] = { -1,0,1,1,1,0,-1,-1 };
    while (K != 0 && tree.size() != 0) {
 
        // 봄, 여름
        vector < pair < Point, int > > tempTree;
        vector < int > deadTree;
        sort(tree.begin(), tree.end(), compPoint);
        int treeCount = tree.size();
        for (int i = 0; i < treeCount; i++) {
            Point tPoint = tree[i].first;
            int tValue = tree[i].second;
            if (ground[tPoint.x][tPoint.y] >= tValue) {
                ground[tPoint.x][tPoint.y] -= tValue;
                tree[i].second += 1;
                tempTree.push_back(tree[i]);
            }
            else {
                deadTree.push_back(i);
            }
        }
 
        
        int deadTreeCount = deadTree.size();
        for (int i = 0; i < deadTreeCount; i++) {
            Point tPoint = tree[deadTree[i]].first;
            int tValue = tree[deadTree[i]].second;
            ground[tPoint.x][tPoint.y] += tValue / 2;
        }
 
 
        // 가을
        treeCount = tempTree.size();
        for (int i = 0; i < treeCount; i++) {
            Point tPoint = tempTree[i].first;
            int tValue = tempTree[i].second;
            if (tValue % 5 == 0) {
                int cx, cy;
                for (int k = 0; k < 8; k++) {
                    cx = tPoint.x + dx[k];
                    cy = tPoint.y + dy[k];
                    if (cx >= 0 && cy >= 0 && cx < N && cy < N) {
                        tempTree.push_back(make_pair(Point(cx, cy), 1));
                    }
                }
            }
        }
 
        // 겨울
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ground[i][j] += s2d2[i][j];
            }
        }
 
        // 죽은 트리 없애고 수정하기.
        tree.clear();
        tree = tempTree;
        K--;
    }
 
    cout << tree.size();
    return 0;
}

행복하세요 화이팅