[ 삼성 SW역량 평가 16235 ] 나무 재테크 (C++)

[ 관련 지식 ]

<Priority Queue> https://twpower.github.io/93-how-to-use-priority_queue-in-cpp

 

[ 난이도 ]

★★★

 

[ 문제 링크 ]

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

 

[ 문제 풀이 ]

문제 자체는 큰 어려움이 없다.

각각 봄, 여름, 가을, 겨울에 맞는 함수를 짜주고 반복시키면 된다.

다만 한가지 문제는 정확히 풀었는데 시간이 많이 부족한 문제였다.

아래 예제는 시간이 초과하는 예제지만.. 덱을 사용하여 구현하면 시간이 빨라진다고 한다.

 

만든 사용자 함수는 크게

1. Load_Input() : 입력을 받아오고 모든 땅의 초기 비료를 5로 초기화하는 부분이다.

 

2. Spring() : 봄에 해당하는 함수이다. 우선순위 큐를 사용하여 나이가 어린 큐부터 빠지게 설정하였다.

 

3. Summer() : 봄에 죽은 나무들을 비료로 바꿔주는 함수이다.

 

4. Fall() : 번식 나무로 분류된 나무들을 NPQ큐에 넣어주는 함수이다.

 

5. Winter() : 로봇이 비료를 추가하게 한다.

 

6. Solve() : 해당 년도 만큼 반복 후 PQ의 사이즈 즉 살아있는 나무의 수를 세어준다.

 

[ 소스 코드 ]

// 헤더파일을 불러옵니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
 
// 맵의 최대크기는 10입니다.
#define Max_Size 11
 
// (나이,(X좌표,Y좌표))의 우선큐를 PQ,NPQ를 만듭니다
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> PQ,NPQ;
 
// 번식할나무와 죽을 나무를 저장하는 벡터를 만듭니다.
vector< pair<int, pair<int, int>>> Spread, Die;
 
// A : 더해질 양분, Anergy : 땅의 양분 현황.
int A[Max_Size][Max_Size];
int Anergy[Max_Size][Max_Size];
int N, M, K;
 
// 번식할 방향을 배열로 나타냄.
int dx[8] = { -1,-1,-1,0,1,1,1,0 };
int dy[8] = { -1,0,1,1,1,0,-1,-1 };
 
// 입력을 받아옵니다.
void Load_Input()
{
    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            // 땅의 초기 비료는 5입니다.
            cin >> A[i][j];
            Anergy[i][j] = 5;
        }
    }
    // 살아있는나무 PQ에 나무의 초기 좌표와 나이를 넣어줍니다.
    for (int k = 0; k < M; ++k)
    {
        int x, y,age;
        cin >> x >> y >> age;
        PQ.push(make_pair(age, make_pair(x, y)));
    }
}
 
// 봄
void Spring()
{
    // 큐가 다 빠질 때 까지 실행
    while (!PQ.empty())
    {
        // 정보를 빼내고
        int x = PQ.top().second.first;
        int y = PQ.top().second.second;
        int age = PQ.top().first;
        // 큐를 뺴줌
        PQ.pop();
 
        // 성장할 수 있으면
        if ((Anergy[x][y] - age) >= 0)
        {
            // NPQ에 새롭게 갱신된 나무를 추가시켜줌
            Anergy[x][y] -= age;
            NPQ.push(make_pair(age+1, make_pair(x, y)));
 
            // 5의 배수면 번식나무로 분류함
            if ((age + 1) % 5 == 0)
            {
                Spread.push_back(make_pair(age+1, make_pair(x, y)));
            }
        }
        // 위 경우가 아닐경우 죽는 나무로 분류함.
        else
        {
            Die.push_back(make_pair(age, make_pair(x, y)));
        }
    }
}
 
// 여름
void Summer()
{
    // 죽은나무들을 에너지로 만듬.
    for (int i = 0; i < (int)Die.size(); ++i)
    {
        int x = Die.at(i).second.first;
        int y = Die.at(i).second.second;
        int age = Die.at(i).first;
 
        Anergy[x][y] += age / 2;
    }
}
 
// 가을
void Fall()
{
    // 번식할 나무들을 새로운 나무리스트에 올림.
    for (int i = 0; i < (int)Spread.size(); ++i)
    {
        int x = Spread.at(i).second.first;
        int y = Spread.at(i).second.second;
 
        for (int j = 0; j < 8; ++j)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];
 
            if (nx<1 || nx > N || ny <1 || ny >N) continue;
 
            NPQ.push(make_pair(1, make_pair(nx, ny)));
        }
    }
}
 
// 에너지를 추가시켜줌.
void Winter()
{
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            Anergy[i][j] = Anergy[i][j] + A[i][j];
        }
    }
}
 
// 해결
void Solve()
{
    for (int i = 0; i < K; ++i)
    {    // 년수 만큼 4계절을 지나고
        Spring();
        Summer();
        Fall();
        Winter();
        // 빈 PQ 큐와 NPQ 큐를 바꿔주고 반복
        swap(PQ, NPQ);
        // 번식나무와 죽은 나무를 초기화시켜줌
        Die.clear();
        Spread.clear();
    }
    // 살아있는 나무를 카운트해줌
    cout << PQ.size();
}
 
int main()
{
    // 입력을 받아옴
    Load_Input();
    // 해결.
    Solve();
    // 정상종료
    return 0;
}