[algorithm] 백준 - 낚시왕

 

삼성 SW기출 문제이자 시뮬레이션이며, 시간 제한이 1초라는 것을 유의해야한다

 

상어의 크기는 모두 다 다르다는 특징이 있다.

격자의 크기는 R,C 상어의 수 m,

상어 위치 r,c 속력 s ,이동방향 d, 크기 z이다.

 

낚시왕이 1번열의 한칸 왼쪽에 있다. 가장 오른쪽 열에 위치하면 이동을 멈춘다.

1초 동안 아래 연산이 이루어진다.

 

1. 낚시왕이 오른쪽으로 한칸 이동한다. 

낚시왕이 낚시를 끝낼 때까지 연산이 이루어져야하므로

while문 안에서 아래의 작업을 수행한다.

 

int king = 0, answer = 0;
    while(king != C){
        king++;
        answer += catchShark(king);
        moveShark();
        eatShark();
    }

 

2. 낚시왕이 위치해있는 열에서 가장 가까운 상어를 잡는다.

잡으면 격자판에서 사라지므로 삭제한다.

 

int catchShark(int king){
    for(int i = 1; i <= R; i++){
        if(water[i][king] != -1){
            int size = shark[water[i][king]].size;
            shark.erase(shark.find(water[i][king]));
            return size;
        }
    }
    return 0;
}

 

3. 상어가 이동한다.

상어가 격자판 경계를 넘으면 이동 방향을 바꿔서 속력을 유지한 채로 이동한다.

속도는 칸/초이다.

 

방향	좌표	반대방향
1 위	(-1,0)	2 아래
2 아래	(1,0)	1 위
3 오른쪽	(0,1)	4 왼쪽
4 왼쪽	(0,-1)	3 오른쪽

 

상어가 이동하는 연산에서 가장 시간이 많이 소요된다.

3중 반복문이 수행되므로 최대 100*100*1000*100 = 십억번의 연산으로

시간초과가 날 수 있다.

따라서 만일 방향이 왼쪽 오른쪽인 경우 s % (R*2 - 2)

위 아래인 경우 s %(C*2 -2)

로 연산을 줄일 수 있다.

 

 

 

void moveShark(){
    for(unordered_map<int,info>::iterator i = shark.begin(); i != shark.end();i++){
        int copyS = i->second.s;
        if(i->second.direction >= 3) copyS = copyS%(2*C - 2);
        else copyS = copyS%(2*R - 2);
        int count = 0;
        while(1){
            if(copyS == count) break;
            count++;
            int dx = i->second.r + directx[i->second.direction];
            int dy = i->second.c + directy[i->second.direction];
            if(dx >= 1 && dy >= 1 && dx <= R && dy <= C){
                i->second.r = dx;
                i->second.c = dy;
            }
            else{
                i->second.direction = turn[i->second.direction];
                i->second.r += directx[i->second.direction];
                i->second.c += directy[i->second.direction];
            }
        }
    }
}

 

4. 크기가 큰 상어가 나머지 상어를 잡아먹는다.

해당 위치에 있는 상어의 크기를 배열에 대입하고,

그 위치에 다른 상어가 존재할 때 크기 비교 후,

작은 상어는 삭제하고, 큰 상어는  배열에 대입한다.

 

void eatShark(){
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            water[i][j] = -1;
        }
    }
    for(unordered_map<int,info>::iterator i = shark.begin(); i != shark.end();){
        int r = i->second.r;
        int c = i->second.c;
        if(water[r][c] != -1 && shark[water[r][c]].size < i->second.size){
            shark.erase(shark.find(water[r][c]));
            water[r][c] = i->first;
        }
        else if(water[r][c] != -1 && shark[water[r][c]].size > i->second.size){
            shark.erase(i++);
            continue;
        }
        else if(water[r][c] == -1){
            water[r][c] = i->first;
        }
        i++;
    }
}

 

전체 코드는 이렇다.

 

//낚시왕
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

struct info{
    int r,c,s,direction,size;
};
int water[101][101];
int directx[] = {0,-1,1,0,0};
int directy[] = {0,0,0,1,-1};
int turn[] = {0,2,1,4,3};
int R,C,m;
unordered_map<int,info> shark;
void moveShark(){
    for(unordered_map<int,info>::iterator i = shark.begin(); i != shark.end();i++){
        int copyS = i->second.s;
        if(i->second.direction >= 3) copyS = copyS%(2*C - 2);
        else copyS = copyS%(2*R - 2);
        int count = 0;
        while(1){
            if(copyS == count) break;
            count++;
            int dx = i->second.r + directx[i->second.direction];
            int dy = i->second.c + directy[i->second.direction];
            if(dx >= 1 && dy >= 1 && dx <= R && dy <= C){
                i->second.r = dx;
                i->second.c = dy;
            }
            else{
                i->second.direction = turn[i->second.direction];
                i->second.r += directx[i->second.direction];
                i->second.c += directy[i->second.direction];
            }
        }
    }
}
void eatShark(){
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            water[i][j] = -1;
        }
    }
    for(unordered_map<int,info>::iterator i = shark.begin(); i != shark.end();){
        int r = i->second.r;
        int c = i->second.c;
        if(water[r][c] != -1 && shark[water[r][c]].size < i->second.size){
            shark.erase(shark.find(water[r][c]));
            water[r][c] = i->first;
        }
        else if(water[r][c] != -1 && shark[water[r][c]].size > i->second.size){
            shark.erase(i++);
            continue;
        }
        else if(water[r][c] == -1){
            water[r][c] = i->first;
        }
        i++;
    }
}
int catchShark(int king){
    for(int i = 1; i <= R; i++){
        if(water[i][king] != -1){
            int size = shark[water[i][king]].size;
            shark.erase(shark.find(water[i][king]));
            return size;
        }
    }
    return 0;
}
void print(){
    cout << "\n";
    for(unordered_map<int,info>::iterator i = shark.begin(); i != shark.end(); i++){
        cout << i->second.r << " " << i->second.c << " " << i->second.size << "\n";
    }
}
int main(void){
    cin >> R >> C >> m;
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            water[i][j] = -1;
        }
    }
    for(int i = 0; i < m; i++){
        info info;
        cin >> info.r >> info.c;
        cin >> info.s >> info.direction >> info.size;
        water[info.r][info.c] = info.size;
        shark.insert({info.size,info});
    }
    int king = 0, answer = 0;
    while(king != C){
        king++;
        answer += catchShark(king);
        moveShark();
        eatShark();
    }
    cout << answer;
}