[백준 17143][C++] 낚시왕 (Gold 2)

[문제보기]

 17143. 낚시왕

17143번: 낚시왕

 

[풀이과정]

상어에 대한 정보를 저장하기 위해 {상어.좌표y, x, 속력, 방향, 크기, 생존유무}를 담고있는 구조체를 만들었다. 

그리고 vector<int> map함수를 만들었는데, 배열 형식으로 미리 크기를 정해주었다. vector로 만들어준 이유는 

상어를 이동 후 한 칸에 여러마리 상어가 있을 경우를 알기 위해 vector로 만들어주었다.

 

전체 코드 형식은 

1. 낚시

2. 상어 이동

3. 상어 죽이기

로 3단계로 나누어서 작동을 한다.

 

1. 낚시 / Catch_Fisher(int Cur) 함수

현재 낚시꾼의 위치를 Cur변수로 보내준다. 그리고 행에 대해서 확인을 통해 제일 위에 있는(낚시꾼과 가까이 있는) 

상어를 잡는다. 잡았다라는 표시는 상어를 죽이는 걸로 대체했다.(Shark[].live = false)

 

2. 상어 이동 / Move_Shark() 함수

맨 처음 map에 대해 clear()를 해준다. 모든 상어 비워주기

 

그리고 Shark[]에 담겨있는 정보를 가지고 상어를 이동해 주는데, 이 때 최악의 경우 속력이 100이고, 상어가 10000마리가 있을 때, 10^7이 되고, 낚시꾼이 움직이는 경우 100까지 해주면 연산은 10^9가 형성이 되어 1초가 넘게된다.

그렇기 때문에 속력에 대한 숫자를 줄어줘야하는데

예를 들어 방향이 1 or 2인 상어에 대해 자기 자리로 오는 수는 ((R-1)*2) 라는 규칙이 만들어지는데, 

R = 3일 때, 1 = 5,

R = 4일 때, 1 = 7,

R = 5일 때, 1 = 9와 같아진다.

이렇게 속력에 대한 숫자를 줄어준 뒤 상어를 이동시켜준다. 이동 시킬 때, map밖으로 나가게 되면 Inverse_Dir() 함수를 

이용하여 방향을 반대로 바꿔준다.

 

3. 상어죽이기 / Kill_Shark() 함수

Kill_Shark() 함수를 이용하여 상어를 죽이게 되는데, map[][]를 검사를 하여 사이즈가 2이상이 되는 곳에 대해서

상어 크기에 맞게 정렬을 한 후 한 마리 빼고 모두 죽이면 된다.

 

[소스코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct _SHARK{
    int y;
    int x;
    int speed;
    int dir;
    int size;
    bool live;
} SHARK;

int R, C, M, ans = 0;
vector<int> map[101][101];
SHARK Shark[10000];
pair<int,int> movdir[5] = {{0,0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};

bool cmp(int a, int b){
    return Shark[a].size > Shark[b].size;
}

int Inverse_Dir(int dir){
    if(dir == 1) return 2;
    else if(dir == 2) return 1;
    else if(dir == 3) return 4;
    return 3;
}

void Catch_Fisher(int Cur){
    for(int i = 1; i<=R; i++){
        if(!map[i][Cur].empty()){
            int Shark_num = map[i][Cur][0];
            ans += Shark[Shark_num].size;
            Shark[Shark_num].live = false;
            return;
        }
    }
}

void Move_Shark(){
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            map[i][j].clear();
        }
    }

    for(int i=0; i<M; i++){
        if(Shark[i].live == false) continue;

        int y = Shark[i].y;
        int x = Shark[i].x;
        int dir = Shark[i].dir;
        int speed = Shark[i].speed;
        if(dir == 1 || dir == 2){
            speed = speed %((R-1)*2);
        }
        else{
            speed = speed %((C-1)*2);
        }

        int ny = y, nx = x;
        while(1){
            if(speed == 0) break;

            ny = y + movdir[dir].first;
            nx = x + movdir[dir].second;

            if(0 < ny && ny <= R && 0 < nx && nx <= C){
                y = ny;
                x = nx;
                speed--;
            }
            else{
                dir = Inverse_Dir(dir);
            }
        }
        

        Shark[i].y = ny;
        Shark[i].x = nx;
        Shark[i].dir = dir;
        map[ny][nx].push_back(i);
    }
}

void Kill_Shark(){
    for(int i=1; i<= R; i++){
        for(int j=1; j<=C; j++){
            if(map[i][j].size() >= 2){
                sort(map[i][j].begin(), map[i][j].end(), cmp);
                for(int k=1; k<map[i][j].size(); k++){
                    int idx = map[i][j][k];
                    Shark[idx].live = false;
                }
            }
        }
    }

}


int main(){
    cin >> R >> C >> M;
    if(M == 0){
        cout << 0;
        return 0;
    }

    for(int i=0; i<M; i++){
        cin >> Shark[i].y >> Shark[i].x >> Shark[i].speed >> Shark[i].dir >> Shark[i].size;
        Shark[i].live = true;
        map[Shark[i].y][Shark[i].x].push_back(i);
    }

    for(int i=1; i<=C; i++){
        Catch_Fisher(i);
        if(i == C) break;
        
        Move_Shark();
        Kill_Shark();

    }

    cout << ans;
}

 

[해결 과정 중 실수한 부분]

코드를 확실하게 다 짰지만, 시간 초과가 나와 시간을 줄이는 부분을 생각해봤는데, 속력에 대해 숫자를 줄일 수 있다는 

것을 찾고 이 부분을 고치니 통과가 되었다.