[백준/C++] 17143번 낚시왕

백준

 

---

🤔문제 이해

상어는 주어진 속도와 방향으로 1초마다 이동하고, 같은 위치에 두마리 이상이 이동된 경우 사이즈가 큰 상어만 남게 된다.

낚시왕도 1초마다 오른쪽으로 이동해 낚시왕이 위치한 열에 있는 상어 중 가장 위에 있는 상어만 잡아 올리고 잡은 상어의 크기를 모두 합한 값을 출력하는 문제이다.

---

💡첫번째 아이디어

단순하게 구현하는 문제인데 시간이 적게 걸리게 하기 위해서는 상어를 이동시킬 때 격자판의 경계를 만났을 때마다 방향을 바꾸는게 아닌 한번에 옮기는 식을 세워야 한다고 생각했다. 여러 경우를 시뮬레이션 해보고 식을 세웠다. 

 

🔥풀이🔥

격자판의 크기를 넘어간다면 처음 넘어가고 그 이후부터는 (격자판 크기-1)로 나눈 나머지가 규칙적으로 0, 1, ... (격자판 크기 -1) , ...,1, 0이 되게 해주었다.

 

격자판에서 +방향으로 이동하는 상어(아래쪽, 위쪽)는

현재 위치에서 속도를 더했을 때 격자판의 크기(아래쪽-C, 위쪽-R)보다 작거나 같으면 단순히 더하기만 해주고, 같을 땐 방향도 바꿔준다.

격자판을 넘어가면 위 규칙에 맞게 새로운 속도 값을 기존 속도 + (격자 크기- (격자 크기 - 현재 위치 + 1))로 바꿔준다.

바꾼 속도값을 (격자크기 -1)로 나눈 나머지가 홀수면 방향이 반대, 위치는 격자 크기 - ( 새 속도 % (격자 크기-1) )이 된다.

바꾼 속도값을 (격자크기 -1)로 나눈 나머지가 짝수면 방향은 그대로, 위치는 새 속도 % (격자크기 -1) +1 이 된다.

 

격자판에서 -방향으로 이동하는 상어(왼쪽, 아래쪽)는

현재 위치에서 속도를 뺐을 때 격자판의 크기(왼쪽-C, 아래쪽-R)보다 작거나 같으면 단순히 빼주기만 하고, 같을 땐 방향도 바꿔준다.

격자판을 넘어가면 위 규칙에 맞게 새로운 속도 값을 기존 속도 + ((격자크기-1) - 현재위치)로 바꿔준다.

바꾼 속도값을 (격자크기-1)로 나눈 나머지가 홀수면 방향이 반대, 위치는 새 속도 % (격자크기 -1) +2이 된다.

바꾼 속도값을 (격자크기-1)로 나눈 나머지가 짝수면 방향은 그대로, 위치는 (격자 크기-1) - (새 속도 % (격자크기-1))이 된다.

 

이동한 상어의 위치는 tmp라는 임시 배열에 저장해주고 이동할 tmp의 위치에 이미 상어가 있다면 크기를 비교해 큰 것만 남게 해준다.

다 이동시킨 뒤엔 tmp를 기존 배열에 옮겨주고 tmp는 초기화해준다.

매 초마다 낚시꾼이 위치한 열의 가장 가까이 있는 상어를 잡고 그 크기를 다 더해주면 끝!

 

설명이 다소 복잡할 수 있지만 어느 한 위치에 있는 상어를 여러 속도로 이동시킬 때 위 방식을 적용해보면 어떤 느낌인지 알게 될 거다.

 

 

❌트러블 슈팅

각 방향마다 격자판의 크기와 상어의 위치를 계산할 때 필요한 좌표값 하나가 다른 점을 생각하지 못했다. +방향과 -방향끼리 동작이 같다고 해서 복붙만 했던게 실수였고, 입력받은 변수 중에 격자크기를 나타내는 R,C와 상어의 위치를 나타내는 r,c랑 헷갈렸었다. 코드가 길어지고 입력 부분을 미리 짜두고 상어 이동 식을 세우다보니 까먹은 거 같다..ㅎ

---

#include <iostream>
#include <cstring>

using namespace std;

int R, C, M;
int r, c, s, d, z;
pair<int, pair<int, int>> map[102][102]; //속력, 이동방향, 크기
pair<int, pair<int, int>> tmp[102][102];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> R >> C >> M;
    for (int i = 0; i < M; i++) {
        cin >> r >> c >> s >> d >> z;
        map[r][c] = {s, {d, z}};
    }
    int cnt = 0;
    for (int k = 1; k <= C; k++) {
        for (int i = 1; i <= R; i++) {
            if (map[i][k].second.first == 0) continue;
            else {
                map[i][k].second.first = 0;
                cnt += map[i][k].second.second;
                break;
            }
        }
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                int y = i;
                int x = j;
                int speed = map[i][j].first;
                int direct = map[i][j].second.first;
                int size = map[i][j].second.second;
                if (direct == 0) continue;
                switch (direct) {
                    case 1:
                        if ((y - speed) > 1) {
                            y = y - speed;
                        } else if ((y - speed) == 1) {
                            y = y - speed;
                            direct = 2;
                        } else {
                            int ny = speed + ((R - 1) - y);
                            if (ny / (R - 1) % 2 == 1) {
                                direct = 2;
                                y = ny % (R - 1) + 2;
                            } else {
                                y = (R - 1) - (ny % (R - 1));
                            }
                        }

                        if (tmp[y][x].second.second != 0) {
                            if (tmp[y][x].second.second < size) {
                                tmp[y][x] = {speed, {direct, size}};
                            }
                        } else {
                            tmp[y][x] = {speed, {direct, size}};
                        }
                        break;
                    case 2:
                        if ((y + speed) < R) {
                            y = y + speed;
                        } else if ((y + speed) == R) {
                            y = y + speed;
                            direct = 1;
                        } else {
                            int ny = speed + (R - (R - y + 1));
                            if (ny / (R - 1) % 2 == 1) {
                                direct = 1;
                                y = R - (ny % (R - 1));
                            } else {
                                y = (ny % (R - 1)) + 1;
                            }
                        }

                        if (tmp[y][x].second.second != 0) {
                            if (tmp[y][x].second.second < size) {
                                tmp[y][x] = {speed, {direct, size}};
                            }
                        } else {
                            tmp[y][x] = {speed, {direct, size}};
                        }
                        break;
                    case 3:
                        if ((x + speed) < C) {
                            x = x + speed;
                        } else if ((x + speed) == C) {
                            x = x + speed;
                            direct = 4;
                        } else {
                            int nx = speed + (C - (C - x + 1));
                            if (nx / (C - 1) % 2 == 1) {
                                direct = 4;
                                x = C - (nx % (C - 1));
                            } else {
                                x = (nx % (C - 1)) + 1;
                            }
                        }

                        if (tmp[y][x].second.second != 0) {
                            if (tmp[y][x].second.second < size) {
                                tmp[y][x] = {speed, {direct, size}};
                            }
                        } else {
                            tmp[y][x] = {speed, {direct, size}};
                        }
                        break;
                    case 4:
                        if ((x - speed) > 1) {
                            x = x - speed;
                        } else if ((x - speed) == 1) {
                            x = x - speed;
                            direct = 3;
                        } else {
                            int nx = speed + ((C - 1) - x);
                            if (nx / (C - 1) % 2 == 1) {
                                direct = 3;
                                x = nx % (C - 1) + 2;
                            } else {
                                x = (C - 1) - (nx % (C - 1));
                            }
                        }

                        if (tmp[y][x].second.second != 0) {
                            if (tmp[y][x].second.second < size) {
                                tmp[y][x] = {speed, {direct, size}};
                            }
                        } else {
                            tmp[y][x] = {speed, {direct, size}};
                        }
                        break;
                }
            }

        }
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                map[i][j] = tmp[i][j];
            }
        }
        memset(tmp, 0, sizeof(tmp));
    }
    cout << cnt;
}