[C/C++] BOJ 16235 :: 나무 재테크

BOJ 16235 :: 나무 재테크

문제 링크 : https://www.acmicpc.net/problem/16235

나의 풀이

문제를 구현할 때 특별히 어려운 기술을 요구하는 문제는 아니다.

문제를 잘 읽고 그대로 코딩하면 된다!

* 코드를 다 짜고 한 가지 간과했었던 점을 발견했는데

가을의 경우, 갱신을 하면서 배열을 탐색하여, 지금 갱신된 값들도 탐색을 하는 오류를 범한 점이다.

물론, 갱신되는 나무의 나이는 1이고 탐색 시에는 나무의 나이가 5의 배수인 것을 탐색하기 때문에 결과에는 아무런 지장이 없지만, 이건 아주 중대한 실수였다..!!!

따라서, 봄에 나무가 존재하는 위치를 새로운 벡터에 저장해두고, 가을에 이 벡터를 탐색함으로써 문제를 해결하였다.

* 죽게 되는 나무를 벡터에서 제거하기 위하여, pop_back() 함수를 사용해

원래 나무의 개수에서 살아남은 나무의 개수를 뺀 만큼 반복하여 뒤의 나무들을 모두 삭제하였다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_16235/BOJ_16235.cpp

// 백준알고리즘 16235번 :: 나무 재테크
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
struct info
{
    vector<int> old; // 현재 땅에 심어진 나무들의 나이를 담는 벡터
    int tnum; // 현재 땅에 심어진 나무들의 개수
    int food; // 현재 땅의 양분
}typedef INFO;
 
INFO ground[12][12];
 
int food_table[12][12];
int N, M, K, ans;
int dx[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };
int dy[8] = { 0, 0, -1, 1, -1, 1, -1, 1 };
 
void simulate()
{
    vector<pair<int, int>> v;
 
    // 봄
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            // 나무가 있으면, 나이가 어린 나무부터 나이만큼 양분을 먹는다.
            // 나이만큼 양분을 먹지 못하면 죽는다.
            if (ground[i][j].tnum != 0)
            {
                v.push_back(make_pair(i, j));
                sort(ground[i][j].old.begin(), ground[i][j].old.end());
                int tnum = ground[i][j].tnum;
                for (int k = 0; k < tnum; k++)
                {
                    // 나이만큼 양분을 먹을 수 있다.
                    if (ground[i][j].old[k] <= ground[i][j].food)
                    {
                        ground[i][j].food -= ground[i][j].old[k];
                        ground[i][j].old[k]++;
                    }
                    // 나이만큼 양분을 먹을 수 없다. => 나무가 죽는다
                    // 여름
                    else
                    {
                        for (int l = tnum - 1; l >= k; l--) {
                            ground[i][j].food += ground[i][j].old[l] / 2;
                            ground[i][j].old.pop_back();
                        }
                        ground[i][j].tnum = k;
                        break;
                    }
                }
            }
        }
    }
    
    // 가을
    for (int i = 0; i < (int)v.size(); i++)
    {
        int x = v[i].first;
        int y = v[i].second;
        int tnum = ground[x][y].tnum;
        for (int k = 0; k < tnum; k++)
        {
            if (ground[x][y].old[k] % 5 == 0)
            {
                for (int l = 0; l < 8; l++)
                {
                    int mx = x + dx[l];
                    int my = y + dy[l];
 
                    if (mx < 1 || mx > N || my < 1 || my > N) continue;
                    ground[mx][my].old.push_back(1);
                    ground[mx][my].tnum++;
                }
            }
        }
    }
 
    // 겨울
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            ground[i][j].food += food_table[i][j];
        }
    }
}
void findtnum()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            ans += ground[i][j].tnum;
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int x = 0, y = 0, z = 0;
 
    cin >> N >> M >> K;
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            ground[i][j].food = 5;
            ground[i][j].tnum = 0;
        }
    }
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> food_table[i][j];
        }
    }
 
    for (int i = 0; i < M; i++)
    {
        cin >> x >> y >> z;
        ground[x][y].old.push_back(z);
        ground[x][y].tnum++;
    }
 
    for(int i = 0; i < K; i++)
        simulate();
 
    findtnum();
 
    cout << ans;
 
    return 0;
}