[17143번] 낚시왕(런타임 에러 발생 예제 포함)

문제

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계인 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

 

이 문제는 이번 상반기 삼성 코딩테스트 기출 문제이다.

 

문제접근법.

 

1. 가장 가까운 물고기를 확인하기 위해서는 물고기 정보를 저장하는 2차원 자료구조가 존재해야 한다.

2. 물고기들을 매초마다 이동시키는 것은 시간 복잡도에 문제가 발생하므로, 물고기가 같은 방향, 같은 자리로 되돌아오는 규칙을 찾는다. 물고기들의 이동 반경이 똑같기 때문에 분명히 규칙이 있다.

3. 물고기들이 같은 자리에 있다면 가장 크기만 남게 되므로, 위에서 말한 2차원 자료구조를 우선순위 큐로 사용한다.

 

 

 물고기들을 이동시킬 때, 주의해야 한다. 이동된 물고기의 좌표는 또 다시 재사용되지 않기 위해서 다른 자료 구조에 넣어줘야 한다. 참고로, 한 문제내에서 자료 구조를 여러 번 선언해서 사용하는 것은 런타임 에러를 발생시킬 수 있다. 런타임 에러를 발생하는 코드는 다음과 같다.

 

 

해설 코드(C++). 런타임 에러 발생(자료구조 세 가

 이 코드를 보면, 2차원 우선순위 큐의 탐색 시간을 줄이기 위해서, 필수적으로 필요한 벡터 자료구조 이외에 1개 더 선언했다. 필수적으로 필요한 벡터 자료구조는 물고기가 이동한 후에 위치를 가지고 있는 자료구조이다. 이 코드는 모든 예제를 통과하지만, 런타임 에러를 발생시킨다. 백준 알고리즘에서 런타임 에러는 다음과 같은 이유로 발생할 수 있다.

 

'한 문제 내에서 필요하지 않는 자료 구조를 탐색 시간을 줄이기 위해서 여러 번 선언할 때'

 

위 사실을 유념해두고, 런타임 에러가 발생한다면, 탐색 시간을 줄이기 위해서 선언한 자료 구조없이 코드를 작성해야 한다.

 

아래의 코드는 런타임 에러가 발생하지 않는 코드이다. 필수적으로 필요한 자료 구조만을 사용해서 코드를 작성했다.

 

해설 코드(C++).

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
 
typedef struct shark {
    int s, d, z;
    shark(int _s, int _d, int _z) :s(_s), d(_d), z(_z) {};
}shark;
 
typedef struct myfunc {
    bool operator()(shark s1, shark s2) {
        return s1.z < s2.z;
    }
};
 
int answer = 0;
int R, C, M;
int r,c, s, d, z;
int tmp_r, tmp_c, tmp_s, tmp_d, tmp_z;
int op[5][2] = { {},{-1,0},{1,0},{0,1},{0,-1} };
priority_queue<shark, vector<shark>, myfunc> p_q[101][101];
priority_queue<shark, vector<shark>, myfunc> m_p_q[101][101];
 
int main() {
    freopen("input.txt", "r", stdin);
    cin >> R >> C >> M;
 
    if (M == 0) {
        cout << 0 << endl;
        return 0;
    }
 
    for (int m = 1; m <= M; m++) {
        cin >> r >> c >> s >> d >> z;
        if (d <= 2) {
            s = s % (2 * (R - 1));
        }
        else {
            s = s % (2 * (C - 1));
        }
        p_q[r][c].push(shark(s, d, z));
    }
 
    //Fisher Move
    for (int i = 1; i <= C; i++) {
        // Fish Catch
        for (int j = 1; j <= R; j++) {
            if (p_q[j][i].size() == 1) {
                answer += p_q[j][i].top().z;
                p_q[j][i].pop();
                break;
            }
        }
 
        // Fish Move
        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                if (p_q[r][c].size() == 1) {
                    tmp_r = r;
                    tmp_c = c;
                    tmp_s = p_q[r][c].top().s;
                    tmp_d = p_q[r][c].top().d;
                    tmp_z = p_q[r][c].top().z;
                    p_q[r][c].pop();
 
                    // ROW
                    if (tmp_d <= 2) {
                        for (int t_s = 0; t_s < tmp_s; t_s++) {
                            if (tmp_r == 1) 
                                tmp_d = 2;
                            if (tmp_r == R)
                                tmp_d = 1;
                            tmp_r += op[tmp_d][0];
                        }
                    }
                    // COL
                    else {
                        for (int t_s = 0; t_s < tmp_s; t_s++) {
                            if (tmp_c == 1)
                                tmp_d = 3;
                            if (tmp_c == C)
                                tmp_d = 4;
                            tmp_c += op[tmp_d][1];
                        }
                    }
                    m_p_q[tmp_r][tmp_c].push(shark(tmp_s, tmp_d, tmp_z));
                }
            }
        }
 
        // MAP CHANGE
        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                if (m_p_q[r][c].size() != 0) {
                    p_q[r][c].push(m_p_q[r][c].top());
                    while (!m_p_q[r][c].empty()) m_p_q[r][c].pop();
                }
            }
        }
    }
 
    cout << answer << endl;
    return 0;
}