[BOJ] 16235 : 나무 재테크

문제 링크

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

16235번: 나무 재테크

단순한 구현 문제.

풀이

초기 양분은 모든 칸이 5로 동일하다는 문제 조건을 안읽어서 계속 못풀고 있었다. 항상 느끼는 거지만 문제를 잘 읽어야한다 *^^*

각 칸에 여러개의 나무가 있을 수도 있으므로 벡터를 2차원으로 선언해서 각 좌표마다 나무의 정보를 저장했다.

그리고 계절마다 함수를 만들어서 계절마다 작업을 해주었다.

1. 봄 & 여름

봄에는 나무가 자신의 나이만큼 양분을 먹고 나이가 1증가한다.

"만약 나무가 여러개인 경우 어린 나무부터 양분을 섭취한다." 라는 조건이 있기 때문에 봄이 시작되기전 모든 나무벡터를 나이순으로 정렬해주어야 한다.

양분이 부족해서 먹지못한 나무는 즉시 죽고 양분이 되어야하기때문에

임의의 (i, j) 좌표의 나무를 기준으로, 만약에 k번째 나무부터 양분을 못한다고 하면 k번째 나무부터 마지막 나무까지는 모두 죽고 양분이 되어야한다. 죽는 나무들의 나이 / 2 의 총합을 저장해두고 (i, j) 좌표의 양분에 추가해준다.

그리고 죽은 나무들은 벡터에서 삭제한다.

이렇게하면 봄과 여름을 동시에 처리할 수 있다.

void Spring_Summer() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (tree[i][j].empty())
				continue;
			int nutrition = 0;
			int k;
			vector<int> alive;
			for (k = 0; k < tree[i][j].size(); k++) {
				if (B[i][j] >= tree[i][j][k]) { //양분이 남아있으면
					B[i][j] -= tree[i][j][k];
					tree[i][j][k]++; //나이 1증가
					alive.push_back(tree[i][j][k]);
				}
				else break;
			}
			for (int t = k; t < tree[i][j].size(); t++)
				nutrition += (tree[i][j][t] / 2);
			tree[i][j].clear();
			tree[i][j] = alive;
			B[i][j] += nutrition;
		}
	}
}​

 

여기서 B 배열은 각 좌표마다 남아있는 양분의 양이다.

2. 가을

가을에는 나이가 5의 배수인 나무들이 번식을 하는 시기이다.

각 좌표를 돌면서 만약 나이가 5인 나무가 있다면 인접한 지역에 나이가 1인 나무를 추가해주면 된다.

인접한 지역의 좌표는 dx[], dy[] 배열을 만들어서 인접한 지역의 좌표를 찾아줬다.

void Fall() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (tree[i][j].empty())
				continue;
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] % 5 == 0) { //번식 가능
					for (int p = 0; p < 8; p++) {
						pair<int, int> adjacent = { i + dy[p], j + dx[p] };
						if (is_ok(adjacent.first, adjacent.second))
							tree[adjacent.first][adjacent.second].push_back(1);
					}
				}
			}
		}
	}
}

3. 겨울

겨울에는 초기에 입력받은 A배열을 기준으로 모든 좌표에 A배열에 저장된 값만큼 양분을 충전해주면 된다.

void Winter() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			B[i][j] += A[i][j];
		}
	}
}

 

이 함수들을 이용해서 코드를 작성하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 10 + 5;
int A[MAX_N][MAX_N];
int B[MAX_N][MAX_N];
int dx[] = { 0,1,0,-1,1,-1,1,-1 };
int dy[] = { 1,0,-1,0,1,1,-1,-1 };
vector<int> tree[MAX_N][MAX_N];
int N, M, K;
 
bool is_ok(int y, int x) {
    if (x <= 0 || x > N || y <= 0 || y > N)
        return false;
    return true;
}
 
void Spring_Summer() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (tree[i][j].empty())
                continue;
            int nutrition = 0;
            int k;
            vector<int> alive;
            for (k = 0; k < tree[i][j].size(); k++) {
                if (B[i][j] >= tree[i][j][k]) { //양분이 남아있으면
                    B[i][j] -= tree[i][j][k];
                    tree[i][j][k]++; //나이 1증가
                    alive.push_back(tree[i][j][k]);
                }
                else break;
            }
            for (int t = k; t < tree[i][j].size(); t++)
                nutrition += (tree[i][j][t] / 2);
            tree[i][j].clear();
            tree[i][j] = alive;
            B[i][j] += nutrition;
        }
    }
}
 
void Fall() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (tree[i][j].empty())
                continue;
            for (int k = 0; k < tree[i][j].size(); k++) {
                if (tree[i][j][k] % 5 == 0) { //번식 가능
                    for (int p = 0; p < 8; p++) {
                        pair<int, int> adjacent = { i + dy[p], j + dx[p] };
                        if (is_ok(adjacent.first, adjacent.second))
                            tree[adjacent.first][adjacent.second].push_back(1);
                    }
                }
            }
        }
    }
}
 
void Winter() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            B[i][j] += A[i][j];
        }
    }
}
 
void sort_tree() {
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            sort(tree[i][j].begin(), tree[i][j].end());
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
            B[i][j] = 5;
        }
    }
    for (int i = 0; i < M; i++) {
        int y, x, z;
        cin >> y >> x >> z;
        tree[y][x].push_back(z);
    }
 
    while (K--) {
        sort_tree();
        Spring_Summer();
        Fall();
        Winter();
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            ans += tree[i][j].size();
        }
    }
    cout << ans << "\n";
    return 0;
}