[백준] 16235 - 나무 재태크

문제를 조금씩 잘못 이해해서 좀 오래걸렸던 문제...

우선순위 큐를 사용하라는 말이 많았는데 나는 굳이 그렇게 특별히 알고리즘을 사용하지는 않았다

1. 초기에 주어진 양분에서 입력된 나무의 위치를 넣는다.

2. 봄이 찾아온다. 여기서 2중 for문으로 순회하며 나무가 있는 곳은 sort하여 어린 나무 순서대로 양분을 먹인다.

양분을 먹이다 남은 양분보다 많은 나이가 나오면, 그순간부터 dead 구조체 배열에 순차적으로 담아주고, 나무의 갯수와 그 map에서 죽은 나무를 제거한다.

3. 여름이 찾아온다. dead 구조체 배열에 담긴 죽은 나무들을 하나씩 map에 나이의 절반을 더해준다.

4. 가을이 찾아온다. 다시 2중 for문을 순회하며 나이가 5이상인 나무 주변의 8개 방향에 나이 1인 나무를 뒤에다 넣어준다.

5. 겨울이 찾아온다. map에 A 배열에 담긴 양분을 각 위치에 더해준다.

이렇게 순차적으로만 해주면 충분히 통과 가능하다.

#include <iostream>
#include <algorithm>
#define MX 12
using namespace std;
 
struct DEAD {
    int x, y, age;
}dead[MX*MX*MX*MX*MX*MX];
 
int A[MX][MX], map[MX][MX], tree[MX][MX][MX*MX*MX*MX*MX];
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int N, M, K, dab, pos;
 
int main(void)
{
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            cin >> A[i][j];
            map[i][j] = 5;
        }
    for (int i = 0; i < M; i++)
    {
        int x, y, z;
        cin >> y >> x >> z;
        tree[y][x][++tree[y][x][0]] = z;
    }
    for (int t = 1; t <= K; t++)
    {
        pos = -1;
        for (int i = 1; i <= N; i++) // 봄
            for (int j = 1; j <= N; j++)
                if (tree[i][j][0])
                {
                    sort(tree[i][j] + 1, tree[i][j] + (tree[i][j][0] + 1));
                    int len = tree[i][j][0];
                    for (int z = 1; z <= len; z++)
                        if (tree[i][j][z] <= map[i][j])
                        {
                            map[i][j] -= tree[i][j][z];
                            tree[i][j][z]++;
                        }
                        else
                        {
                            dead[++pos].x = j; dead[pos].y = i; dead[pos].age = tree[i][j][z];
                            tree[i][j][z] = 0;
                            tree[i][j][0]--;
                        }
                }
        for (int i = 0; i <= pos; i++) // 여름
            map[dead[i].y][dead[i].x] += dead[i].age / 2;
        for (int i = 1; i <= N; i++) // 가을
            for (int j = 1; j <= N; j++)
            {
                int len = tree[i][j][0];
                for (int z = 1; z <= len; z++)
                    if (!(tree[i][j][z] % 5))
                        for (int d = 0; d < 8; d++)
                        {
                            int nx = j + dx[d], ny = i + dy[d];
                            if (nx <= 0 || ny <= 0 || nx > N || ny > N) continue;
                            tree[ny][nx][++tree[ny][nx][0]] = 1;
                        }
            }
        for (int i = 1; i <= N; i++) // 겨울
            for (int j = 1; j <= N; j++)
                map[i][j] += A[i][j];
    }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            dab += tree[i][j][0];
    cout << dab << endl;
    return 0;
}