C++ 문제풀이 - 나무 재테크 (백준 16235)

심심풀이로 인터넷에서 찾은 프로그래밍 문제들을 좀 풀어보고 있습니다. 여기서 소개할 것은 나무 재테크라는 문제로서, 나무들의 인구 역학을 이산수학 모형을 통해 알아보는 내용을 담고 있죠.

 

16235번: 나무 재테크

 

정사각형 모양의 격자 구조를 상정하고, 각 칸에 있는 나무들의 갯수가 연도별로 어떻게 달라지는지 계산하는 프로그램을 만들어야 합니다. 나무가 성장하기 위해 토양으로부터 소모하는 양분의 개념이 도입되어 있는데요. 나이만큼 양분을 소모하여 1살 더 먹을 수 있지만, 충분한 양분이 없다면 나무는 죽어서 자라날 새싹들을 위한 거름이 된다는 설정이 있습니다.

 

반응형

 

이 모형에서 1년은 4계절 (봄, 여름, 가을, 겨울)로 나뉘어져 있고, 계절별로 서로 다른 이벤트가 발생하여 나무의 개체 수에 영향을 줍니다. 봄에는 나무들이 성장을 하고, 여름에는 양분 부족으로 죽었던 나무들이 양분을 제공하죠. 각 나무는 5년마다 가을에 번식을 해서 개체 수를 늘립니다. 마지막으로 겨울에는 땅 주인이 추가로 양분을 제공합니다.

 

C++ 소스 코드입니다.

 

test_bj16235.cpp [다운로드]

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<chrono>

// 각 나무의 정보을 담고 있는 구조체
typedef struct Tree {
    bool alive;  // 살아있는지의 여부
    int age;     // 나이
} Tree;

/* 나무의 나이를 비교하는 함수로서
 * EcoTable 클래스 내의 trees 벡터를
 * 정렬하는 데 사용됩니다. */
bool compare_age(Tree tree_1, Tree tree_2) {
    if (tree_1.age < tree_2.age) {
        return true;
    } else {
        return false;
    }
}

class EcoTable {
  private :

    int N;  // 정사각형 땅 크기

    int M;  // 처음에 심은 나무의 갯수

    // 나무의 개체 수 변화를 알고자 하는 년 수
    int K;

    // 각 칸에 함유된 토양의 양분
    int **resource;

    /* 매년 겨울에 땅 주인이 각 칸에
     * 추가하는 양분 */
    int **A;

    /* 각 칸에 있는 나무들에 대한
     * 정보를 저장하기 위한 벡터 */
    std::vector<Tree> **trees;

    bool initialized;

  public :

    // 생성자
    EcoTable() {
        initialized = false;
    }

    // 소멸자
    ~EcoTable() {
        free_array();
    }

    // 입력 파일의 이름을 받아서 초기화
    void init(const char *fname) {
        free_array();

        FILE *fin;
        fin = fopen(fname, "r");
        if (fin == NULL) {
            return;
        }

        // N, M, K 의 값 입력
        fscanf(fin, "%d %d %d", &N, &M, &K);

        // 동적 메모리 할당 및 초기화
        resource = new int *[N + 1];
        A = new int *[N + 1];
        trees = new std::vector<Tree> *[N + 1];
        for (int r = 1; r <= N; r++) {
            resource[r] = new int [N + 1];
            A[r] = new int [N + 1];
            trees[r] = new std::vector<Tree> [N + 1];

            for (int c = 1; c <= N; c++) {
                // 처음에 각 칸에 함유된 양분은 5
                resource[r][c] = 5;

                fscanf(fin, "%d", &A[r][c]);

                trees[r][c].clear();
            }
        }

        // 처음에 심어진 나무들에 대한 정보 입력
        for (int jtr = 0; jtr < M; jtr++) {
            Tree tree_new;
            tree_new.alive = true;

            int r_in, c_in;
            fscanf(fin, "%d %d %d", &r_in, &c_in, &tree_new.age);
            trees[r_in][c_in].push_back(tree_new);
        }
        
        fclose(fin);

        initialized = true;
    }

    /* main 함수에서 호출하는 함수로서,
     * 시간 진화를 계산하고, 살아있는 나무의 갯수 출력 */
    void evolve() {
        // K년만큼 시간 진화
        for (int iy = 0; iy < K; iy++) {
            next_spring();  // 봄
            next_summer();  // 여름
            next_autumn();  // 가을
            next_winter();  // 겨울
        }

        // 살아있는 나무의 총 갯수
        int n_trees_total = 0;
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                // 각 칸에 있는 모든 나무들에 대한 for 반복문
                for (int itr = 0; itr < trees[r][c].size(); itr++) {
                    if (trees[r][c].at(itr).alive) {
                        n_trees_total += 1;
                    }
                }
            }
        }

        fprintf(stdout, "  %d\n", n_trees_total);
    }

    // 이벤트 : 봄
    void next_spring() {
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                int number_trees =
                    static_cast<int>(trees[r][c].size());
                if (number_trees == 0) {
                    continue;
                }

                /* 어린 나무들이 먼저 오도록 벡터 정렬
                 * 이렇게 해서 어린 나무들이 먼저 양분을 소모 */
                std::sort(trees[r][c].begin(),
                          trees[r][c].end(),
                          compare_age);

                // 각 칸에 있는 모든 나무들에 대한 for 반복문
                for (int itr = 0; itr < number_trees; itr++) {
                    if (!trees[r][c].at(itr).alive) {
                        continue;
                    }

                    if (resource[r][c] >= trees[r][c].at(itr).age) {
                        // 나이만큼의 양분이 있으면 성장
                        resource[r][c] -= trees[r][c].at(itr).age;
                        trees[r][c].at(itr).age += 1;
                    } else {
                        // 양분이 부족하면 사망
                        trees[r][c].at(itr).alive = false;
                    }
                }
            }
        }
    }

    // 이벤트 : 여름
    void next_summer() {
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                // 각 칸에 있는 모든 나무들에 대한 for 반복문
                for (int itr = 0; itr < trees[r][c].size(); itr++) {
                    if (trees[r][c].at(itr).alive) {
                        continue;
                    }

                    /* 죽은 나무의 나이에 따라
                     * 양분을 추가 */
                    resource[r][c] +=
                        (trees[r][c].at(itr).age -
                         trees[r][c].at(itr).age % 2) / 2;

                    trees[r][c].at(itr).age = 0;
                }
            }
        }
    }

    // 이벤트 : 가을
    void next_autumn() {
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                // 각 칸에 있는 모든 나무들에 대한 for 반복문
                for (int itr = 0; itr < trees[r][c].size(); itr++) {
                    // 나무의 나이가 5의 배수인 경우에만 번식
                    if (!trees[r][c].at(itr).alive ||
                        trees[r][c].at(itr).age % 5 != 0) {
                        continue;
                    }

                    // 인접한 8개의 칸에 나무 추가
                    for (int jr = -1; jr <= 1; jr++) {
                        int ir = r + jr;
                        if (ir < 1 || ir > N) {
                            continue;
                        }

                        for (int jc = -1; jc <= 1; jc++) {
                            int ic = c + jc;
                            if (ic < 1 || ic > N) {
                                continue;
                            }

                            if (jr == 0 && jc == 0) {
                                continue;
                            }

                            Tree tree_new;
                            tree_new.alive = true;
                            tree_new.age = 1;
                            trees[ir][ic].push_back(tree_new);
                        }
                    }
                }
            }
        }
    }

    // 이벤트 : 겨울
    void next_winter() {
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                resource[r][c] += A[r][c];
            }
        }
    }

    // 동적으로 할당된 메모리 해제
    void free_array() {
        if (!initialized) {
            return;
        }

        for (int r = 1; r <= N; r++) {
            delete [] resource[r];
            delete [] A[r];
            delete [] trees[r];
        }

        delete [] resource;
        delete [] A;
        delete [] trees;

        initialized = false;
    }
};

// main 함수
int main(int argc, char *argv[]) {
    char fname_input[200];
    if (argc > 1) {
        /* 명령행 인자가 있는경우,
         * 실행파일 다음에 오는 인자를 입력파일 이름으로 지정 */
        strcpy(fname_input, argv[1]);
    } else {
        /* 명령행 인자가 없으면,
         * 실행파일 이름이 input.txt 라고 가정 */
        strcpy(fname_input, "input.txt");
    }

    EcoTable ecotab;

    const clock_t begin_time = clock();
    auto t_start =
        std::chrono::high_resolution_clock::now();

    // 초기화
    ecotab.init(fname_input);
    // 시간 진화
    ecotab.evolve();

    const clock_t end_time = clock();
    auto t_end = std::chrono::high_resolution_clock::now();

    double elapsed_time_ms =
        std::chrono::duration<double, std::milli>(t_end-t_start).count();

    fprintf(stdout, "\n");
    fprintf(stdout, "  elapsed CPU time (ms) : %e\n",
        1e+3 * double(end_time - begin_time) / CLOCKS_PER_SEC);
    fprintf(stdout,
        "  elapsed Wall clock time (ms) : %e\n", elapsed_time_ms);

    return 0;
}

 

격자 공간에 있는 양분과 나무 수에 대한 초기조건을 입력받아서, 시간 변화를 계산하기 위한 EcoTable 클래스를 도입했습니다. 봄, 여름, 가을, 겨울에 발생하는 이벤트를 구현하기 위한 멤버 함수들인 next_spring, next_summer, next_autumn, next_winter 가 정의되어 있죠. 시간 진화를 계산하고자 하는 년 수만큼 반복문에서 이 함수들을 호출하는 방식입니다.

 

백준 웹사이트에 있는 예제 입력과 같은 형식으로 텍스트 파일을 작성하고, 이를 프로그램의 입력파일로 넘겨주면 결과값을 얻을 수 있습니다. 웹사이트에서 예제로 나온 8개의 문제는 일단 다 맞췄네요. clang C++ 컴파일러 (clang++)로 -std=c++11 옵션과 함께 빌드했을 때, CPU 시간은 0.5 밀리초 (ms), 실제 경과시간은 1 밀리초 (ms) 내외로 나왔습니다. 시간 제한의 정확한 기준은 모르겠습니다만, 0.3초에 비하면 매우 짧은 시간안에 프로그램이 실행되었으니 퇴짜맞을 수준은 아니라고 추측해봅니다.

 

여기서는 프로그램을 실행할 때 들어가는 명령행 인자 (argc, argv)를 통해서 입력파일의 이름을 지정해 주고 있습니다. C언어 및 C++ 명령행 인자에 대해서는 다음 포스팅에 좀 더 자세히 소개되어 있습니다.

 

Command-line arguments (C/C++ 명령행 인자)