[16235] 나무 재테크

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

16235번: 나무 재테크

<문제>

문제가 길고, 구현해야 하는 것도 많다. 대략 다음을 구현해야 하는 문제이다.

1. 하나의 칸에 여러개의 나무가 존재할 수 있으며, 같은 칸중 어린나무부터 양분을 자신의 나이만큼 먹는다.

1-1 : 먹을 양분이 없다면, 나무는 죽고 죽은 나무가 양분이된다.

1-2 : 먹을 양분이 있다면, 나무는 양분을 먹고 나이가 1 증가한다.

2. 나이가 5의 배수일때, 인접한 칸에 나이1의 나무를 생성한다.

 

그외에는 맵에 단순한 연산으로 커버할 수 있다. 이제 구현해야하는걸 하나씩 따져보자.

1. '하나의 칸에 여러개의 나무가 존재할 수 있다' -> 3차원으로 관리해주어야 한다. 이를 조금 더 편리하게 관리하기 위해서 vector<int>tree[][]의 형태로 선언하였다.

2. 같은 칸중 어린 나무부터 양분을 먹는다 -> 같은 칸에 여러개의 나무가 있다면, '정렬'해야한다.

3. 나무의 나이가 5의 배수일때, 인접한 칸에 나이1의 나무를 생성한다 -> 8방향 방향데이터로, bfs에서 다음 정점을 탐색할때처럼 비슷하게 구현하면 된다.

 

시뮬레이션이 끝난 후, 구해야하는 답은 모든 벡터[i][j]의 사이즈의 합이다.

<소스코드>

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, m, k;
int a[11][11];//겨울마다 추가되는 양분
int food[11][11];//양분
vector<int>tree[11][11];
vector<int>dead[11][11];
vector<int>temp;
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };//12시부터 시계방향, 총 8방향
int main(void) {
    int i, j, x, y;
    scanf("%d %d %d", &n, &m, &k);
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]); 
            food[i][j] = 5;//초기 양분은 5
        }
    }
    for (i = 1; i <= m; i++) {
        int A,B,C;
        scanf("%d %d %d", &A, &B, &C);// 행, 열, 나이
        tree[A][B].push_back(C);
    }
    while (k--) {
        //봄
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (tree[i][j].size() == 0)continue;
                sort(tree[i][j].begin(), tree[i][j].end());//어린 나무부터
                for (x = 0; x < tree[i][j].size(); x++) {    
                    if (food[i][j] >= tree[i][j][x]) {//충분한 양분이 있다면    
                        food[i][j] -= tree[i][j][x];//나이만큼 양분을 먹고
                        temp.push_back(tree[i][j][x] + 1);//증가된 나이를 저장한다
                    }
                    else { //양분이 없다면
                        dead[i][j].push_back(tree[i][j][x]);//죽은 나무 목록에 나이를 넣는다
                    }
                }
                tree[i][j].clear();
                for (x = 0; x < temp.size(); x++) {
                    tree[i][j].push_back(temp[x]);
                }
                temp.clear();
            }
        }
        //여름
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (dead[i][j].size() == 0)continue;
                for (x = 0; x < dead[i][j].size(); x++) {
                    food[i][j] += (dead[i][j][x] / 2);//양분을 (죽은 나무 나이)/2 만큼 증가
                }
                dead[i][j].clear();
            }
        }
        //가을
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (tree[i][j].size() == 0)continue;
                for (x = 0; x < tree[i][j].size(); x++) {
                    if (tree[i][j][x] % 5 == 0) {//나이가 5의 배수일때
                        for (y = 0; y < 8; y++) {//8방향으로
                            int ty, tx;
                            ty = i + dy[y];
                            tx = j + dx[y];
                            if (ty <= 0 || tx <= 0 || ty > n || tx > n)continue;//땅을 벗어나면 자라지 않는다
                            tree[ty][tx].push_back(1);//나이가 1인 나무를 생성한다.
                        }
                    }
                }
            }
        }
        //겨울
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                food[i][j] += a[i][j];//양분을 추가
            }
        }
        /*
        printf("-------------------\n");
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                for (x = 0; x < tree[i][j].size(); x++)
                    printf("[%d][%d] : %d", i,j,tree[i][j][x]);
            }
            printf("\n");
        }
        printf("-------------------\n");
        */
    }
    //k년이 지난 후    
    int answer = 0;
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            answer += tree[i][j].size();
            //printf("<%d>", answer);
        }
    }
    printf("%d", answer);
    return 0;
}