[백준][C++] 17143번: 낚시왕 <237>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

17143번: 낚시왕

 

생각의 흐름

아... 캐어렵다... 구현할 부분이 생각보다 많고, 생각해야 될점도 많다...

 

먼저 문제의 진행방식을 크게 3단계로 나눌 수 있다.

    1. 배열 초기화 하기

    2. 사람이 상어 낚시하기

    3. 모든 상어 움직이고, 잡아먹기

 

▶ 배열 초기화 하기

이때 맨 처음 초기화 가 중요하다. 초기화 할때 나머지 연산을 수행하지 않으면 시간초과가 발생한다.

우선 코드를 보면 다음과 같다.

int r, c, s, d, z;
for (int i = 1; i <= M; i++) {
    cin >> r >> c >> s >> d >> z;
    
    if (d == 1 || d == 2) {
        s %= (R - 1) * 2;
    } else if (d == 3 || d == 4) {
        s %= (C - 1) * 2;
    }
    
    Sharks[r][c].push_back(Shark(r, c, s, d, z));
}

input으로  r, c, s, d, z를 받는다. r 과 c 는 상어의 위치값이니 그냥 저장하면된다.

하지만 speed 값인 s는 그냥 저장하면 안되다!

 

문제의 제한시간이 1초이다.

최악의 경우 상어수가 10000마리인데, 10000마리가 1000의 스피드, 즉 1000칸씩 움직이게 될 경우 10000 * 1000 = 10^7 만큼의 시간이 걸리게된다.

사람이 1열부터 C열까지 움직일 때 마다 해야 하니 10^7 * 10^2(C의 최대값) 이 되어 최악의 경우 10^9만큼의 연산을 하게 된다.

 

그냥 speed를 저장하면 안된다는 소리이다.

 

따라서 %(나머지 연산자)를 활용한다.

 

예를 들어보자.

위 그림에서 C번(2, 4) 상어의 경우 speed가 10이 되면, 모든 상어가 이동하는동안 시작점과 동일한 위치에 멈추게 된다.

Speed가 20, 30, 40 일 때도 마찬가지이다. 이동하고 나면 자기 자신의 자리에 도착하게 되있다.

 

같은 원리로 speed가 1000이여도 시작점(2, 4) -> 도착점(2, 4) 즉, 자기 자신의 위치를 유지하게 된다.

 

만약 speed가 1001 이였다면 매우 쉽게 한칸만 이동한다고 생각하면 편하다.

시작점(2, 4) -> 도착점(2, 3) 이 되는 것 이다!

 

이쯤 되면 왜 나머지 연산을 해야 하는지 감이 올것같다.

위 예시에서 C상어는 좌, 우로 움직이기 때문에 (너비 - 1) * 2를 해준값인 10으로 나누면 된다.

만약 상, 하 로 움직였다면 (높이-1) * 2 를 해주면 된다.

 

이것만 하면 나머지는 편하다.

 

▶ 사람이 상어 낚시하기

void fishing(int index) {
    for (int i = 1; i <= R; i++) {
        if (!Sharks[i][index].empty()) {
            totalSize += Sharks[i][index].front().size;
            Sharks[i][index].pop_back();
            return;
        }
    }
}

 

▶ 모든 상어 움직이고, 잡아먹기

void moveAndKillShark() {
    vector<Shark> newSharks[MAX][MAX];

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (Sharks[i][j].empty()) { continue; }
            Shark &nowShark = Sharks[i][j].front();
            int& nowX = nowShark.x;
            int& nowY = nowShark.y;
            int nowSpeed = nowShark.speed;
            int& nowDirection = nowShark.direction;

            while(nowSpeed--) {
                int nx = nowX + dir[nowDirection][0];
                int ny = nowY + dir[nowDirection][1];

                if(nx < 1 || ny < 1 || nx > R || ny > C) {
                    nowDirection = changeDir(nowDirection);
                }
                nowX += dir[nowDirection][0];
                nowY += dir[nowDirection][1];
            }
            if(!newSharks[nowX][nowY].empty()) {
                if(nowShark.size > newSharks[nowX][nowY].front().size){
                    newSharks[nowX][nowY].pop_back();
                    newSharks[nowX][nowY].push_back(nowShark);
                }
            }else {
                newSharks[nowX][nowY].push_back(nowShark);
            }
        }
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            Sharks[i][j] = newSharks[i][j];
        }
    }
}

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 102

int R, C, M;
int totalSize;

class Shark {
public:
    int x, y;
    int speed;
    int direction;
    int size;
public:
    Shark(int x, int y, int speed, int direction, int size) : x(x), y(y), speed(speed), direction(direction),
                                                              size(size) {}
};

vector<Shark> Sharks[MAX][MAX];
int dir[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};

void fishing(int index) {
    for (int i = 1; i <= R; i++) {
        if (!Sharks[i][index].empty()) {
            totalSize += Sharks[i][index].front().size;
            Sharks[i][index].pop_back();
            return;
        }
    }
}

int changeDir(int d) {
    if (d == 1) return 2;
    if (d == 2) return 1;
    if (d == 3) return 4;
    if (d == 4) return 3;
}

void moveAndKillShark() {
    vector<Shark> newSharks[MAX][MAX];

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (Sharks[i][j].empty()) { continue; }
            Shark &nowShark = Sharks[i][j].front();
            int& nowX = nowShark.x;
            int& nowY = nowShark.y;
            int nowSpeed = nowShark.speed;
            int& nowDirection = nowShark.direction;

            while(nowSpeed--) {
                int nx = nowX + dir[nowDirection][0];
                int ny = nowY + dir[nowDirection][1];

                if(nx < 1 || ny < 1 || nx > R || ny > C) {
                    nowDirection = changeDir(nowDirection);
                }
                nowX += dir[nowDirection][0];
                nowY += dir[nowDirection][1];
            }
            if(!newSharks[nowX][nowY].empty()) {
                if(nowShark.size > newSharks[nowX][nowY].front().size){
                    newSharks[nowX][nowY].pop_back();
                    newSharks[nowX][nowY].push_back(nowShark);
                }
            }else {
                newSharks[nowX][nowY].push_back(nowShark);
            }
        }
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            Sharks[i][j] = newSharks[i][j];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C >> M;

    int r, c, s, d, z;
    for (int i = 1; i <= M; i++) {
        cin >> r >> c >> s >> d >> z;
        if (d == 1 || d == 2) {
            s %= (R - 1) * 2;
        } else if (d == 3 || d == 4) {
            s %= (C - 1) * 2;
        }
        Sharks[r][c].push_back(Shark(r, c, s, d, z));
    }

    if (M == 0) {
        cout << 0;
        exit(0);
    }
    for (int i = 1; i <= C; i++) {
        fishing(i);
        moveAndKillShark();
    }

    cout << totalSize;

    return 0;
}