16235

백준 16235번

Link: 16235번: 나무 재테크

---

문제 설명

작년 삼성 기출문제.

IM쪽 기출문제였는데, 여기 시험보고 온 친구들이 전부 못풀어서 멘탈 터져서 온게 기억이 난다.

풀기 시작한게 목요일이었는데, 목요일에는 별 생각없는 노가다로 풀어봤는데 테스트케이스 3개정도 맞히고 나머지 못맞혀서 왜그럴지 고민해봤다.

그렇게 고민해보다 금요일에는 큐를 써서 한 레벨에 대해 전부 뽑아내고 1년을 진행하는 방식으로 해봤다.

그래도 안풀려서 다시 고민했는데, 토요일엔 놀다가 일요일 와서야 풀었다.

매우 단순한 방법으로 해결했는데, 내가 짠 코드대로면 봄에 죽은 나무가 벡터에서는 살아있기 때문에 죽은 나무의 나이를 -1로 바꾸고, 가을에 번식하는 조건에 나이가 0보다 클때로 한정함으로써 풀 수 있었다.

시뮬레이션 문제인것 같은데, 내가 시험볼때 풀어봤던 큐브 문제에 비해서는 훨씬 깔끔하게 답을 구할 수 있었던 문제인것 같다.

뭐 그때의 나였다면 이런 문제 던져줘도 못풀었을것 같긴 하다만…

어쨌든 곧 시험볼때까지 실력을 꾸준히 키워야겠다는 생각이 든다.

---

정답 코드

//
// Created by Keith_Lee on 14/02/2019.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Tree{
    int x, y, age;
};

int N, M, K;

int map[11][11] = {0, };
int winterAdd[11][11] = {0, };
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

queue<Tree> Queue;

int compare(const Tree &t1, const Tree &t2){
    if(t1.age < t2.age){
        return true;
    }
    return false;
}

int BFS(){
    for(int i=0; i<K; i++){
        vector<Tree> lives;
        vector<Tree> deads;

        while(!Queue.empty()){
            lives.push_back(Queue.front());
            Queue.pop();
        }

        sort(lives.begin(), lives.end(), compare);

        for(int j=0; j<lives.size(); j++) {
            if (map[lives[j].x][lives[j].y] >= lives[j].age) { // 봄
                map[lives[j].x][lives[j].y] -= lives[j].age;
                Queue.push({lives[j].x, lives[j].y, lives[j].age + 1});
                lives[j].age++;
            }
            else {
                deads.push_back({lives[j].x, lives[j].y, lives[j].age});
                lives[j].age = -1;
            }

            if(lives[j].age > 0 && lives[j].age % 5 == 0){ // 가을
                for(int k=0; k<8; k++){
                    int nextX = lives[j].x + dx[k];
                    int nextY = lives[j].y + dy[k];

                    if(nextX > 0 && nextX <= N && nextY > 0 && nextY <= N){
                        Queue.push({nextX, nextY, 1});
                    }
                }
            }
        }

        for(int k=0; k<deads.size(); k++){ // 여름
            map[deads[k].x][deads[k].y] += deads[k].age / 2;
        }

        for(int k=1; k<=N; k++){ // 겨울
            for(int l=1; l<=N; l++){
                map[k][l] += winterAdd[k][l];
            }
        }
    }

    return Queue.size();
}

int main(){
    for(int i=0; i<=10; i++){
        for(int j=0; j<=10; j++){
            map[i][j] = 5;
        }
    }

    cin >> N >> M >> K;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> winterAdd[i][j];
        }
    }

    int x, y, z;

    for(int i=0; i<M; i++){
        cin >> x >> y >> z;

        Queue.push({x, y, z});
    }

    cout << BFS() << '\n';

    return 0;
}

---