[C++] 백준/Gold/17143. 낚시왕

문제: 낚시왕 (백준 17143번)

간만에 빡구현 문제를 풀어보았다.
각각의 알고리즘 자체는 어렵지 않지만, 구현할 내용이 많아 세심한 작업이 필요했다.

이 문제의 핵심은 상어의 이동 계산이다. 이동을 시뮬레이션할 때 1칸씩 이동하지 않고 최종 위치를 계산하는 방식으로 처리해야 한다.
이 부분만 주의하면 큰 시간 초과 없이 문제를 해결할 수 있다.

---

상어 클래스 정의

상어의 위치, 속도, 이동 방향, 크기를 관리하기 위해 Shark 클래스를 작성했다.
생성자에서는 초기 위치와 속도, 방향, 크기를 입력받아 초기화한다.
또한, 상어의 이동을 처리하는 Move 메서드를 구현하여 방향과 속도에 따라 위치를 업데이트한다.

class Shark {
public:
    int x, y;
    int speed;
    int direction;
    int size;
    Shark(int r, int c) {
        cin >> speed >> direction >> size;
        y = r;
        x = c;
    }

    void Move(int r, int c) {
        int move = speed;
        if (direction == 1 || direction == 2) {
            move %= (2 * (r - 1)); // 상하 이동
        } else {
            move %= (2 * (c - 1)); // 좌우 이동
        }

        while (move > 0) {
            if (direction == 1) { // 위로 이동
                if (y - move >= 0) {
                    y -= move;
                    move = 0;
                } else {
                    move -= y;
                    y = 0;
                    direction = 2; // 방향 반전
                }
            } else if (direction == 2) { // 아래로 이동
                if (y + move < r) {
                    y += move;
                    move = 0;
                } else {
                    move -= (r - 1 - y);
                    y = r - 1;
                    direction = 1; // 방향 반전
                }
            } else if (direction == 3) { // 오른쪽 이동
                if (x + move < c) {
                    x += move;
                    move = 0;
                } else {
                    move -= (c - 1 - x);
                    x = c - 1;
                    direction = 4; // 방향 반전
                }
            } else if (direction == 4) { // 왼쪽 이동
                if (x - move >= 0) {
                    x -= move;
                    move = 0;
                } else {
                    move -= x;
                    x = 0;
                    direction = 3; // 방향 반전
                }
            }
        }
    }
};

---

주요 로직

1. 초기화
   sea는 상어의 현재 위치를 저장하는 2차원 배열, sharks는 상어 객체를 관리하는 리스트로 설정한다.
   입력값을 바탕으로 상어 객체를 생성하고 sea와 sharks에 추가한다.
2. 낚시왕 이동
   낚시왕은 매 열마다 가장 가까운 상어를 잡는다.
   상어를 잡으면 해당 상어를 리스트와 배열에서 제거하고, 크기를 정답에 더한다.
3. 상어 이동
   상어는 자신의 속도와 방향에 따라 이동하며, 이동 후 위치를 계산한다.
   이동한 위치에 다른 상어가 있다면 크기를 비교해 더 큰 상어만 남긴다.
4. 결과 출력
   모든 열에 대해 낚시와 상어 이동이 끝난 후, 최종적으로 잡은 상어의 크기 합을 출력한다.

---

구현 코드

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int r, c, m; cin >> r >> c >> m;

    vector<vector<Shark*>> sea(r, vector<Shark*>(c, nullptr));
    list<Shark*> sharks;

    // 상어 초기화
    for (int i = 0; i < m; i++) {
        int rr, cc; cin >> rr >> cc;
        rr--, cc--;
        sea[rr][cc] = new Shark(rr, cc);
        sharks.push_back(sea[rr][cc]);
    }

    int answer = 0;

    for (int i = 0; i < c; i++) {
        // 1. 낚시왕이 상어를 잡는다
        for (int j = 0; j < r; j++) {
            if (sea[j][i]) {
                answer += sea[j][i]->size;
                sharks.remove(sea[j][i]);
                delete sea[j][i];
                sea[j][i] = nullptr;
                break;
            }
        }

        // 2. 상어 이동
        vector<vector<Shark*>> new_sea(r, vector<Shark*>(c, nullptr));
        list<Shark*> new_sharks;

        for (auto& shark : sharks) {
            shark->Move(r, c);

            Shark* existing = new_sea[shark->y][shark->x];
            if (existing) {
                if (shark->size > existing->size) {
                    new_sharks.remove(existing);
                    delete existing;
                    new_sea[shark->y][shark->x] = shark;
                    new_sharks.push_back(shark);
                } else {
                    delete shark;
                }
            } else {
                new_sea[shark->y][shark->x] = shark;
                new_sharks.push_back(shark);
            }
        }
        sea = move(new_sea);
        sharks = move(new_sharks);
    }

    cout << answer;
}