[백준 16235][C++] 나무 재테크

문제

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

16235번: 나무 재테크

[참고 질문]

 

풀이 과정

1. 각 계절별 문제 조건에 맞는 함수를 구현한다.

    봄 : 나이가 어린 나무부터 양분 흡수를 진행하기 위해 sorting을 진행한다. 조건을 만족하지 못해 죽는 나무와 살아남은 나무 중 번식 가                 능한 나무를 기록한다.

    여름 : 봄에서 기록된 죽은 나무들을 양분으로 만들어준다.

    가을 : 봄에서 기록된 번식 가능한 나무들을 번식을 진행한다. 범위를 벗어나지 않는 선에서 번식이 진행되도록 구현한다.

    겨울 : S2D2가 새로운 양분을 추가한다.

 

2. 입력된 K 만큼의 해를 보낸 뒤 살아있는 나무의 수를 구한다.

 

 

세부 풀이

봄이 가장 구현이 까다로웠다.

풀이에서 deque를 이용하여 각 위치의 나무의 나이를 기록하도록 사용했다. (소스코드 18 Line : deque <int> trees [10][10];)

해당 deque를 이중 배열 형태로 선언하여 각 위치에서의 sorting 이 가능하도록 구현할 수 있다.

    예를 들어 Row:1, Col:3 위치에 3그루의 나무가 존재할 때, (나무의 나이는 각각 3, 2, 1이라고 가정) trees [1][3] 에는 3, 2, 1 이 존재한다.

    이때 나무의 나이가 어린 나무부터 양분을 흡수해야 하므로 sort(trees [1][3][. begin(), trees [1][3]. end()) 를 진행한 뒤,

    front 위치의 있는 값부터 양분 흡수를 진행한다.

 

흡수할 양분보다 나이가 많은 나무라면 죽게 되는데, 이렇게 죽게 되는 나무를 기록하여 여름에 양분으로 변환할 때  사용한다.

살아남은 나무들 중 올해의 나이가 5의 배수가 되는 나무들을 따로 저장한다. 이를 통해 가을에 반복하여 탐색하는 일 없이 번식하는 나무를 처리할 수 있다.

 

여름과 가을은 봄에서 기록되었던 나무들을 각각 양분으로 만들고, 번식하도록 구현하면 된다.

겨울은 입력받은 값을 각 토양에 더해주도록 구현하면 된다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

deque<int> trees[10][10];
vector<pair<pair<int,int>, int>> dead, parent;

int N,M,K;
int map[10][10];
int S2D2[10][10];


void Input(){
    cin >> N >> M >> K;
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            cin >> S2D2[i][j];
            map[i][j] = 5;
        }
    }
    int ix, iy, iz;
    for(int i=0; i<M; i++){
        cin >> ix >> iy >> iz;
        trees[ix-1][iy-1].push_back(iz);
    }
}

/*
 * 봄
 * 나무의 나이를 증가시키는 함수
 * 나이를 증가시킬 때 같은 칸의 어린 나이부터 양분을 흡수하며,
 * 양분을 흡수하지 못하는 나무는 죽는다.
 */

void spring(){
    dead.clear();
    parent.clear();
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(trees[i][j].size()==0) continue;
            //trees deque 안에는 나무의 나이들이 들어있는데 그중 작은 것 부터
            //처리하기 위해 sort 를 진행한다.
            sort(trees[i][j].begin(),trees[i][j].end());
            int size = trees[i][j].size();
            for(int k=0; k<size; k++){
                int a_age = trees[i][j].front();
                trees[i][j].pop_front();
                if(map[i][j] >= a_age){
                    map[i][j]-= a_age;
                    trees[i][j].push_back(a_age+1);
                    //살아 남는 나무들 중 번식 가능한 경우를 미리 체크하여
                    //parent 에 저장 후 가을때 사용
                    if((a_age+1)%5==0){
                        parent.push_back({{i,j},a_age+1});
                    }
                }
                else{
                    dead.push_back({{i,j},a_age});
                }
            }

        }
    }
}

/*
 * 여름
 * 죽은 나무를 양분으로 변하게 하는 함수
 * 죽은 나무의 나이를 2로 나눈 값이 나무가 있던 칸의 양분이 된다.
 */

void summer(){
    int size = dead.size();
    for(int i=0; i<size; i++){
        int x = dead[i].first.first;
        int y = dead[i].first.second;
        int age = dead[i].second;

        map[x][y] += age/2;
    }
}

/*
 * 가을
 * 나무의 나이가 5의 배수라면 번식
 * 인접한 8칸에 모두 번식한다.
 */
int dir[8][2] = {{1,0},{-1,0},{0,1},{0,-1},
                {1,1},{-1,-1},{1,-1},{-1,1}};

void fall(){
    int size = parent.size();
    for(int i=0; i<size; i++){
        int x = parent[i].first.first;
        int y = parent[i].first.second;
        for(int j=0; j<8; j++){
            int newX = x + dir[j][0];
            int newY = y + dir[j][1];
            if(newX<0 || newX >=N || newY<0 || newY >=N) continue;
            //8방향 중 통과된 위치에 나이가 1인 나무 추가
            trees[newX][newY].push_back(1);
        }
    }
}

/*
 * 겨울
 * S2D2 가 땅에 양분을 추가한다. 각 칸에 추가되는 것은 해당 칸의 양분이므로
 * 저장했던 S2D2 값을 더해준다.
 */

void winter(){
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            map[i][j] += S2D2[i][j];
        }
    }
}

void one_year(){
    spring();
    summer();
    fall();
    winter();
}

void solve(){
    while(K--){
        one_year();
    }

    int ans=0;
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            ans+=trees[i][j].size();
        }
    }

    cout << ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    solve();
    return 0;
}

 

 

결과 및 후기

첫 풀이는 모든 테스트 케이스를 통과했었지만 시간 초과가 발생했다. [제출 번호 45663664]

[참고 질문]을 통해 첫 풀이의 문제를 파악했다. 첫 풀이 때는 tree라는 구조체를 만들어 x, y, age, live를 부여하여 나무들만 따로 vector에 보관했었다. 하지만 이렇게 관리할 경우 tree를 나이순으로 정렬할 때 모든 나무들을 탐색하며 sorting이 진행되며, 이 과정에서 시간 초과가 발생했을 것이라고 생각했다. 그리고 질문자의 코드에서 시간을 추가로 줄일 수 있는 방법이 있었다. 봄에서 나무들을 탐색할 때 가을에 번식할 나무를 미리 찾아서 보관하는 것이다. 이렇게 진행한다면 봄에서 전체 나무 탐색하고, 가을에서 전체 나무를 탐색하는 중복을 피할 수 있다. 이렇게 발견한 문제점들을 고쳐 제출하여 '맞았습니다!!'를 받을 수 있었다. 스스로 풀어내는 것이 훨씬 기분은 좋긴 하지만 정답을 맞힌 여러 사람의 코드를 보고 배울 점이 많다는 것을 한번 더 느꼈다.