C++ 문제풀이 - 낚시왕 (백준 17143)

이번에 풀어본 문제는 낚사왕이라는 문제인데요. 직사각형 모양의 격자 공간에서 낚시꾼이 상어들을 잡아올리는 상황을 이산 시간 시뮬레이션을 통해 알아보는 내용입니다. 이산 시간이라 한 것은, 불연속적으로 떨어진 시각에서의 상태를 다룬다는 의미입니다.

 

17143번: 낚시왕

 

시뮬레이션은 초 단위로 진행되며, 1초당 3개의 이벤트들이 발생하고 이를 구현해야 합니다. 첫번째 단계는 낚시인데요. 격자 공간의 첫번째 행 위에 있는 낚시꾼이 맨 왼쪽에서부터 1초당 오른쪽으로 한칸씩 이동하면서 해당 열에 있는 가장 가까운 상어를 낚아올립니다. 그 다음 단계는 남아 있는 상어들이 각각의 속력과 방향에 따라 이동을 하죠. 이 때 상어가 격자 공간의 끝에 부딧히면, 방향을 반대로 틀어서 이동하게 됩니다. 마지막 단계로서 격자 한 칸당 상어가 2마리 이상 있을 경우 크기가 가장 큰 상어가 나머지를 죄다 잡아먹는다는 설정이 더해져 있습니다.

 

반응형

 

낚시왕이 맨 오른쪽으로 넘어올 때 까지 잡은 상어의 크기의 총 합을 구해서 출력해야 합니다.

 

C++ 소스 코드입니다.

 

test_bj17143.cpp [다운로드]

 

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

/* 각 상어의 상태를 나타내기 위한
 * 전처리 식별자
 * 1 : 살아있는 상태
 * -1 : 다른 상어에게 잡아먹힌 상태
 * 0 : 낚시왕에게 잡힌 상태 */
#define STATUS_ALIVE 1
#define STATUS_EATEN -1
#define STATUS_CAUGHT 0

/* 상어 한마리의 정보를 담고 있는
 * 클래스 객체 */
class Shark {
  public :
    int r;  // 행
    int c;  // 열
    int s;  // 속력
    int d;  // 방향
    int z;  // 크기

    int status;

    Shark() {
        r = 1;
        c = 1;
        s = 0;
        d = 0;
        z = 0;

        status = STATUS_ALIVE;
    }

    ~Shark() {}

    // 1초동안 상어의 이동을 실행하는 함수
    void move(int r_max, int c_max) {
        int v;
        if (d == 1) {
            v = -s;
            r += v;
            while (r < 1 || r > r_max) {
                bounce(r, v, r_max);
            }
            s = -v;
        } else if (d == 2) {
            v = s;
            r += v;
            while (r < 1 || r > r_max) {
                bounce(r, v, r_max);
            }
            s = v;
        } else if (d == 3) {
            v = s;
            c += v;
            while (c < 1 || c > c_max) {
                bounce(c, v, c_max);
            }
            s = v;
        } else if (d == 4) {
            v = -s;
            c += v;
            while (c < 1 || c > c_max) {
                bounce(c, v, c_max);
            }
            s = -v;
        } else {
            return;
        }
    }

    /* 만약 격자의 끝에 도달하면
     * 방향을 반대로 바꾸는 함수 */
    void bounce(int &x, int &v,
                int x_max) {
        if (x < 1) {
            x = 2 - x;
            v = -v;
        } else if (x > x_max) {
            x = x_max - (x - x_max);
            v = -v;
        }
    }
};

/* 벡터를 상어의 크기 순으로 정렬하기
 * 위해 사용되는 함수 */
bool compare_size(Shark &shark1,
                  Shark &shark2) {
    if (shark1.z < shark2.z) {
        return true;
    } else {
        return false;
    }
}

/* 낚시왕이 낚시를 시뮬레이션하는
 * 클래스 객체 */
class FishArena {
  private :

    int R;

    int C;

    int M;

    // 낚시왕의 현재 열
    int c_fisher_;

    /* 지금까지 잡은 상어의
     * 크기의 총 합 */
    int num_catch_;

    /* 격자의 각 칸에서 살아있는
     * 상어의 수 */
    int **num_sharks_;
    // 상어들의 정보를 담고 있는 벡터
    std::vector<Shark> list_sharks_;

    bool initialized_;

  public :

    FishArena() {
        R = 0;
        C = 0;
        M = 0;

        initialized_ = false;
    }

    ~FishArena() {
        free_array();
    }

    /* 초기 상태에 대한 정보를 담은 텍스트 파일의
     * 이름을 받아 초기화하는 함수 */
    void init(const char *fname) {
        free_array();

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

        fscanf(fin, "%d %d %d", &R, &C, &M);

        num_sharks_ = new int *[R + 1];
        for (int ir = 1; ir <= R; ir++) {
            num_sharks_[ir] = new int [C + 1];
            for (int ic = 1; ic <= C; ic++) {
                num_sharks_[ir][ic] = 0;
            }
        }

        for (int ish = 0; ish < M; ish++) {
            Shark shark_now;
            fscanf(fin, "%d %d %d %d %d",
                   &shark_now.r, &shark_now.c,
                   &shark_now.s, &shark_now.d,
                   &shark_now.z);

            shark_now.status = STATUS_ALIVE;

            int ir = shark_now.r;
            int ic = shark_now.c;
            num_sharks_[ir][ic] += 1;

            list_sharks_.push_back(shark_now);
        }

        c_fisher_ = 0;
        num_catch_ = 0;

        std::sort(list_sharks_.begin(),
                  list_sharks_.end(),
                  compare_size);

        fclose(fin);

        initialized_ = true;
    }

    /* 1초동안 일어나는 이벤트들을
     * 시뮬레이션하기 위한 함수 */
    bool next() {
        if (!initialized_) {
            return false;
        }

        if (c_fisher_ == C) {
            return false;
        }

        c_fisher_ += 1;

        // 낚시왕이 상어를 낚아올리는 이벤트
        int jsh = -1;
        int r_caught = R + 1;
        for (int ish = 0; ish < M; ish++) {
            if (list_sharks_.at(ish).c !=
                c_fisher_) {
                continue;
            }

            if (list_sharks_.at(ish).status !=
                STATUS_ALIVE) {
                continue;
            }

            if (list_sharks_.at(ish).r <
                r_caught) {
                r_caught =
                    list_sharks_.at(ish).r;
                jsh = ish;
            }
        }

        if (r_caught <= R) {
            int ir = list_sharks_.at(jsh).r;
            int ic = list_sharks_.at(jsh).c;
            num_sharks_[ir][ic] -= 1;

            list_sharks_.at(jsh).status =
                STATUS_CAUGHT;

            num_catch_ +=
                list_sharks_.at(jsh).z;
        }

        // 상어들이 이동하는 이벤트
        for (int ish = 0; ish < M; ish++) {
            if (list_sharks_.at(ish).status !=
                STATUS_ALIVE) {
                continue;
            }

            int ir, ic;

            ir = list_sharks_.at(ish).r;
            ic = list_sharks_.at(ish).c;
            num_sharks_[ir][ic] -= 1;

            list_sharks_.at(ish).move(R, C);

            ir = list_sharks_.at(ish).r;
            ic = list_sharks_.at(ish).c;
            num_sharks_[ir][ic] += 1;
        }

        /* 격자 한 칸에 여러마리의 상어가 있을 때
         * 크기가 가장 큰 상어가 나머지를 잡아먹는 이벤트 */
        for (int ir = 1; ir <= R; ir++) {
            for (int ic = 1; ic <= C; ic++) {
                if (num_sharks_[ir][ic] <= 1) {
                    continue;
                }

                int n_now = num_sharks_[ir][ic];

                for (int ish = 0; ish < M; ish++) {
                    if (list_sharks_.at(ish).r != ir ||
                        list_sharks_.at(ish).c != ic) {
                        continue;
                    }

                    if (list_sharks_.at(ish).status !=
                        STATUS_ALIVE) {
                        continue;
                    }

                    n_now -= 1;
                    list_sharks_.at(ish).status =
                        STATUS_EATEN;

                    if (n_now == 1) {
                        break;
                    }
                }
            }
        }

        return true;
    }

    int get_num_catch() {return num_catch_;}

    void free_array() {
        if (!initialized_) {
            return;
        }

        list_sharks_.clear();

        for (int ir = 1; ir <= R; ir++) {
            delete [] num_sharks_[ir];
        }
        delete [] num_sharks_;

        initialized_ = false;
    }
};

// 메인 함수
int main(int argc, char *argv[]) {
    char fname_input[200];
    if (argc > 1) {
        strcpy(fname_input, argv[1]);
    } else {
        strcpy(fname_input, "input_17143_0.txt");
    }

    FishArena arena;

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

    arena.init(fname_input);
    bool keep_going = true;
    while (keep_going) {
        keep_going = arena.next();
    }
    int n_catch = arena.get_num_catch();
    fprintf(stdout, "  %d\n", n_catch);

    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;
}

 

일단 백준 웹사이트에 있는 4개의 예제는 다 맞췄네요. clang C++ 컴파일러 (clang++)로 std=c++11 옵션을 줘서 빌드하고, 2019년 맥북 프로에서 돌려보니까 실행 시간은 밀리초 단위로 나옵니다. 시간제한 1초가 정확히 어떤 조건에서인지는 모르겠습니다만, 제가 짠 코드가 속도 면에서 나쁘지는 않은 것 같습니다.

 

참고로 초기 상태에 대한 정보를 담은 파일의 이름을 커맨드 라인에서 지정해줄 수 있는데요. 이들을 명령행 인자라고 부릅니다. C언어 또는 C++ 프로그램에서 명령행 인자를 사용하기 위한 방법에 대해서는 다음 포스팅을 참고하면 좋습니다.

 

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