[백준 16235][C++] 나무 재테크 (Gold4)

[문제보기]

 16235. 나무 재테크

16235번: 나무 재테크

 

[풀이과정]

문제를 읽고 나서 드는 생각은 다른 문제를 풀었을 때처럼 tree에 대한 정보를 그냥 2차원 배열로 만들면 안되고

vector 형식으로 격자판을 만들어야겠다고 생각했다. 왜냐하면 하나의 칸에 나무가 여러 개가 있을 수 있다고 

제시되어 있기 때문에 vector 형태가 생각이 났다.

 

필자가 사용한 변수들은 현재 땅의 양분들이 저장되어 있는 map[][], 겨울이 왔을 때 더해줄 양분의 정보를 가지고

있는 eat_add[][], 그리고 위에서 말했던 나무들의 나이 정보를 가지고 있는 vector tree[][], 그리고 가을이 되었을 때,

번식 위치에 대한 정보를 가지고 있는 movdir[8] 이렇게 4가지 변수를 중점으로 문제를 풀었다.

 

0. vec_sort()

봄 연산에서 어린 나무부터 양분을 섭취한다고 제시되어 있기 때문에 각 땅에 저장한 나무들의 정보들을 오름차순으로

정렬을 시켜준 후 봄/여름 연산을 진행하였다.

 

1. 봄 & 여름(spring_summer())

 -> 주석에 쓰여있다시피 봄이 되면 어린 나무부터 양분을 섭취하고, 자기 나이만큼 먹게 되면 나이가 1 증가하고,

     충분한 양분을 섭취하지 못한 나무들은 죽게 된다. 죽은 나무들은 그 땅에 양분이 되는데 (나이/2)만큼 된다.

 

나무가 양분을 섭취하고 죽은 나무가 땅의 양분이 되는 연산은 한꺼번에 처리하는 것이 더 괜찮다고 생각을 하여 필자는

봄과 여름의 연산을 한 함수 안에서 했다.

이중 for문을 통해 각 땅마다 확인을 하고 각 땅에 있는 나무만큼 양분을 섭취할 수 있게 했다. 양분을 섭취하는 도중 

충분히 양분을 섭취하지 못한 나무가 나오면 break를 하여 그 뒤의 나무들을 죽은 나무로 취급하여 여름 연산을 

진행하였다. (오름차순으로 정렬을 했기 때문에 그 뒤의 나무들은 확인할 필요가 없다)

 

그리고 vector temp 변수를 하나 만들어 양분을 충분히 섭취한 나무들의 나이 정보를 저장하고 여름 연산이 끝난 후 

clear 된 vector tree[][]에 저장해주고, map[][] 배열에 만들어진 양분을 더해준다.

 

2. 가을(fall())

 -> 번식에 대한 연산이다. 나이가 5의 배수인 나무들이 번식을 하게 되는데 번식은 인접한 8칸에 나이가 1인 나무들로 

     번식이 된다.

이중 for문을 통해 각 땅의 나이가 5의 배수인 나무들에 대해 번식을 진행해준다.

인접한 8칸에 대한 연산은 movdir[8] 배열을 사용하여 진행했다.

 

3. 겨울(winter())

 -> 로봇이 돌아다니면서 양분을 추가하는 연산

구현하기 제일 쉬운 부분으로 이전에 입력값을 저장했던 eat_add[][] 배열을 map[][] 배열에 더해주었다.

[소스코드]

//나무 재테크
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, k;
int map[11][11];
int eat_add[11][11];
vector<int> tree[11][11];
pair<int, int> movdir[8] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, 
                                {0, 1}, {1, -1}, {1, 0}, {1, 1}};

void vec_sort(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(tree[i][j].size() == 0) continue;
            sort(tree[i][j].begin(), tree[i][j].end());
        }
    }
}

void spring_summer(){
    //나이만큼 양분 먹고 나이 1증가(어린 나무부터)
    //양분을 못 먹으면 죽음
    //죽은 나무는 양분으로
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(tree[i][j].size() == 0) continue;
            int save = 0;
            int k;
            vector<int> temp;
            //봄 연산
            for(k=0; k<tree[i][j].size(); k++){
                if(tree[i][j][k] <= map[i][j]){
                    map[i][j] -= tree[i][j][k];
                    temp.push_back(tree[i][j][k]+1);
                    continue;
                }
                break;
            }
            
            //여름 연산
            for(int die = k; die<tree[i][j].size(); die++){
                save += (tree[i][j][die]/2);
            }

            tree[i][j].clear();
            for(int l = 0; l<temp.size(); l++){
                tree[i][j].push_back(temp[l]);
            }
            map[i][j] += save;
        }
    }
}

void fall(){
    //나이가 5의 배수 나무들 번식
    //인접한 8칸에 나무 증가

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=0; k<tree[i][j].size(); k++){
                if(tree[i][j][k] % 5 != 0) continue;

                for(int add = 0; add <8; add++){
                    int nexty = i + movdir[add].first;
                    int nextx = j + movdir[add].second;

                    if(nexty <= 0 || n < nexty || nextx <= 0 || n < nextx)
                        continue;
                    
                    tree[nexty][nextx].push_back(1);
                }
            }
        }
    }
}

void winter(){
    //로봇이 돌아다니면서 양분 추가
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            map[i][j] += eat_add[i][j];
        }
    }
}

int main(){
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> eat_add[i][j];
            map[i][j] = 5;
        }
    }

    for(int i=0; i<m; i++){
        int x, y, age;
        cin >> x >> y >> age;
        tree[x][y].push_back(age);
    }

    while(k--){
        vec_sort();
        spring_summer();
        fall();
        winter();
    }

    int cnt = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(!tree[i][j].empty())
                cnt += tree[i][j].size();
        }
    }

    cout << cnt;
}

 

[해결 과정 중 실수한 부분]