백준 17143 - 낚시왕

 

https://www.acmicpc.net/problem/17143

17143번: 낚시왕

문제 설명

---

크기가 R×C인 격자판에서 r은 행, c는 열이고, 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

 

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

 

 

접근 방식

---

삼성의 전형적인 시뮬레이션 문제이다. 각각의 조건을 만족시키며 해답을 찾아나가면 된다. 하지만 조건이 복잡한게 흠이죠....

이 문제에서는 규칙을 지키면서 시간초과가 나지 않도록 하는 것이 가장 중요합니다. 따라서 다음과 같이 진행합니다.

1. 조건이 많으므로 struct를 이용하여 하나로 묶어줍니다.

2. 낚시왕이 한칸 이동한 후 낚시를 진행한다.

3. 잡힌 물고기는 death의 변수를 바꾸어 주고, 물고기가 각자의 속도와 방향에 따라 이동한다.

4. 2-3과정을 반복한다. 열의 끝까지 도착할때까지~

저는 처음에 시간복잡도를 해결하지 못해 시간초과가 났었습니다. ㅠㅠ 시간복잡도에 유의하여 풀어주시면 될거 같습니다. 규칙은 필수!!!!

 

 

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef struct{
    int y;
    int x;
    int Dir;
    int speed;
    int Size;
}Shark;

vector<int>mat[101][101];
vector<Shark>shark;
int c,r,m;
int ans;

void fishing(int human){
    for(int i=1;i<=r;i++){
        if(mat[i][human].size() ==0) continue;
        else{
            ans+=shark[mat[i][human][0]].Size;
            shark[mat[i][human][0]].Size=0;
            shark[mat[i][human][0]].y=0;
            shark[mat[i][human][0]].x=0;
            mat[i][human].clear();
            break;
        }
        
    }
    // print();
    // cout<<"====fishing===="<<"\n";
}
void moving(){
    for(int i=0;i<m;i++){
        if(shark[i].Size ==0) continue;
        int tempy = shark[i].y;
        int tempx = shark[i].x;
        mat[tempy][tempx].clear();
        
    }
    for(int i=0;i<m;i++){
        if(shark[i].Size ==0) continue;
        int cury = shark[i].y;
        int curx = shark[i].x;
        int curDir = shark[i].Dir;
        int curSpeed = shark[i].speed;
        while(curSpeed--){
            //up
            if(curDir==1){
                cury--;
                if(cury == 0){ curDir = 2;  cury=2;}
          
            }
            //down
            else if(curDir==2){
                cury++;
                if(cury == r+1){ curDir = 1;  cury=r-1;} 
            }
            //right
            else if(curDir==3){
                curx++;
                if(curx == c+1){ curDir = 4;  curx=c-1;}
     
            }
            //left
            else if(curDir==4){
                curx--;
                if(curx == 0){ curDir = 3;  curx=2;}
            
            } 
        }
        shark[i].y = cury;
        shark[i].x = curx;
        shark[i].Dir = curDir;
        mat[cury][curx].push_back(i);  
    }
    
}
bool compare(int s1,int s2){
    if(shark[s1].Size > shark[s2].Size) return true;
    else return false;
}
void killing(){
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(mat[i][j].size() >1){
                sort(mat[i][j].begin(),mat[i][j].end(),compare);
                int alive =  mat[i][j][0];
                for(int k=1;k<mat[i][j].size();k++){
                    int idx = mat[i][j][k];
                    shark[idx].Size =0;
                    shark[idx].y=0;
                    shark[idx].x=0;
                }
                mat[i][j].clear();
                mat[i][j].push_back(alive);
            }
        }
    }
}

int main(){
    cin>>r>>c>>m;
    for(int i=0;i<m;i++){
        Shark s;
        cin>>s.y>>s.x>>s.speed>>s.Dir>>s.Size;
        mat[s.y][s.x].push_back(i);
        shark.push_back(s);
    }
    // print();
    // cout<<"====first===="<<"\n";
    if(m==0){
        cout<<0<<"\n";
    }
    else{
        for(int i=1;i<=c;i++){
            fishing(i);
            moving();
            killing();
          	// print();  
        }
        cout<<ans<<"\n";
    }
    return 0;  
}

funny algorithm  ^0^;;