17143. 낚시왕

문제 링크

17143번: 낚시왕

 

풀이

처음 문제를 보면 낚시터를 2차원 배열로 구현하고, 거기에서 상어를 움직이고 잡고 해야 할 것 같다. 하지만 필자는 2차원 배열의 형태로 구현하지 않고, map container를 이용하여 구현하였다. map에서 상어의 위치 좌표를 key로, 상어의 정보(속력, 방향, 크기)를 value로 하여 구현한 것이다. 이렇게 한 이유는 여러 가지가 있는데,

1. map으로 구현하면 낚시터의 상어가 있는 칸만 효율적으로 순회할 수 있다.
2. 한 좌표에는 상어가 한 마리만 존재해야 하므로, map에서 유일하게 존재하는 key의 특성과 일치한다.
3. map의 lower_bound 함수를 이용하면 낚시왕이 잡을 상어를 구할 수 있다.

2차원 배열로도 못 할 건 없겠지만, 아무래도 map으로 구현하는 게 여러모로 효율적이라 생각한 것이다.

typedef struct _shark {
    int speed;
    int dir;
    int size;
} Shark;

map<pair<int, int>, Shark> m;

Shark 구조체를 만들어서 상어의 속력, 방향, 크기를 하나의 변수로 저장하고자 하였다. map container의 key는 상어의 위치, value는 그 외 상어의 정보로 하였다. 이때, pair<int, int>에서 first가 열, second가 행이어야 한다. 열 숫자의 정렬 우선순위가 높아야 lower_bound 함수로 낚시왕이 잡을 상어를 찾기 용이하기 때문이다.

 

주의할 점으로, 상어의 이동을 구현할 때, 속력만큼 1칸씩 움직이며 경계를 확인하도록 구현하면 안 된다. 상어가 최대 10000마리, 그 속력이 최대 1000으로 주어지므로 10000마리의 상어를 정직하게 1000칸씩 하나하나 움직였다간 TLE가 난다(필자가 실제로 이렇게 구현해서 겪었다). 그래서 수학적인 계산으로 상어의 위치를 구해야 한다.

 

그림의 경우를 한번 생각해 보자. R = 4, C = 6이고, 상어의 처음 위치는 (2, 3)이다. 상어의 속력에 따른 위치 변화가 위 그림에 나타나 있다. 보다시피 상어는 두 방향만 반복적으로 맴돌기 때문에, 속력의 값이 아무리 커 봤자 이동 후 위치는 정해져 있음을 알 수 있다. 위 사례에서는 속력이 0, 10, 20일 때 전부 위치가 같음을 보여주며, 마찬가지로 2, 12, 22와 5, 15, 35, 55 모두 위치는 같다. 이를 일반화하면 상어가 위아래로 속력 s만큼 움직인 후 위치는 속력 s % (2 * R - 2)와 같아지고, 좌우로 s만큼 움직일 때는 s % (2 * C - 2)만큼 움직인 후 위치와 같아진다. R과 C의 크기가 각각 최대 100이므로, 이렇게 하면 상어의 속력을 99까지 낮추면서 같은 결과를 얻을 수 있다.

 

일단은 이 정도로도 테스트케이스를 통과하기 충분하지만, 필자는 상어의 이동에 좀 더 최적화를 가했다. 상어를 한 칸씩 이동하는 방식이 아닌, 행 또는 열로부터 상어까지 거리를 따져가며 수학적으로 위치를 구했다. 말로는 설명하기 난잡하니 아래 코드를 차근차근 보며 이해하기 바란다.

 

시간 복잡도

상어 포획 및 이동은 \(C\)번 일어나며, 상어 포획 및 \(M\)마리의 상어 이동 알고리즘에 활용되는 map container는 삽입, 삭제, 탐색 모두 \(O(\log{M})\)의 시간 복잡도를 가진다. 아래의 상어 이동 함수 move의 while문은 연산 방식 특성상 최대 3번 돌아감이 보장된다. 이를 종합하면 시간 복잡도는 \(O(CM \log{M})\)이다.

 

소스코드

#include <iostream>
#include <map>
#include <utility>
using namespace std;

// 상어 구조체
typedef struct _shark {
    int speed;
    int dir;
    int size;
} Shark;

int R, C, M, ans;
int r, c, s, d, z;
map<pair<int, int>, Shark> m;

// 상어 한 마리를 이동하는 함수
void move(Shark& shk, int& main_dir) {
    int speed = shk.speed;
    int main_length;
    if(shk.dir <= 2) main_length = R;
    else main_length = C;
    
    while(speed != 0) {
        if(shk.dir == 1 || shk.dir == 4) {
            if(speed <= main_dir - 1) {
                main_dir -= speed;
                speed = 0;
            }
            else {
                speed -= (main_dir - 1);
                main_dir = 1;
                if(shk.dir <= 2) shk.dir++;
                else shk.dir--;
            }
        }
        else {
            if(speed <= main_length - main_dir) {
                main_dir += speed;
                speed = 0;
            }
            else {
                speed -= (main_length - main_dir);
                main_dir = main_length;
                if(shk.dir <= 2) shk.dir--;
                else shk.dir++;
            }
        }
    }
}

// 상어의 전체적인 이동과 잡아먹는 상황을 처리하는 함수
void moveShark() {
    map<pair<int, int>, Shark> newm;
    for(auto it = m.begin(); it != m.end(); it++) {
        Shark shk = it->second;
        int row = (it->first).second, col = (it->first).first;
        if(shk.dir <= 2) move(shk, row);
        else move(shk, col);
        
        auto newm_it = newm.find(make_pair(col, row));
        if(newm_it == newm.end()) {
            newm.emplace(make_pair(col, row), shk);
        }
        else {
            if((newm_it->second).size < shk.size) {
                newm[make_pair(col, row)] = shk;
            }
        }
    }
    
    m = newm;
}

// 낚시왕이 상어를 잡는 함수
void catchShark(int col) {
    auto it = m.lower_bound(make_pair(col, 1));
    if(it != m.end() && (it->first).first == col) {
        ans += (it->second).size;
        m.erase(it);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> R >> C >> M;
    for(int i = 0; i < M; i++) {
        cin >> r >> c >> s >> d >> z;
        
        // 속력 최적화
        if(d == 1 || d == 2) s %= (2 * R - 2);
        else s %= (2 * C - 2);
        
        Shark shk = {s, d, z};
        m.emplace(make_pair(c, r), shk);
    }
    
    for(int i = 1; i <= C; i++) {
        catchShark(i);
        moveShark();
    }
    
    cout << ans;
    return 0;
}