[백준] 17143. 낚시왕

[문제]

www.acmicpc.net/problem/17143

17143번: 낚시왕

 

[풀이]

 

1. 낚시왕 이동

낚시왕은 열을 기준으로 한칸씩 움직인다. 

 

2. 낚시왕 낚시

낚시왕은 자신이 존재하는 열에서 가장 가까운 물고기를 잡는다.

 

3. 물고기 이동

물고기는 1초에 속력만큼 이동한다. 이 때 범위를 벗어나면 방향을 바꿔서 움직인다.

 

---

시뮬레이션 문제로 낚시하는 함수인 fishing과 물고기가 이동하는 함수인 move를 구현하여 풀었다.

물고기들의 정보를 구조체에 저장하여 1번 물고기부터 M번 물고기까지 차례대로 이동

 

이 때, 한 칸에는 한 마리의 물고기만 존재할 수 있으므로 visited 배열을 사용해 처리한다.

(자신보다 큰 물고기가 있을 경우 죽도록) 

 

[코드]

 

시간 : 44ms

#include <iostream>

#define MAX 101

using namespace std;

struct FISH{
    int x,y,s,d,z;
    bool die;
};

int R,C,M;
int score=0;
int map[MAX][MAX]={0,};
FISH fish[MAX*MAX];
int idx =0;

int dx[5] = {0,-1,1,0,0};
int dy[5] = {0,0,0,1,-1};

void move()
{
    int visited[MAX][MAX]={0,};

    
    for(int i=1;i<=M;i++){
        
        if(fish[i].die) continue;

        int dir = fish[i].d;
        int x = fish[i].x;
        int y = fish[i].y;
        int s = fish[i].s;
        int nx;
        int ny;
        
        while(1){
            
            nx = x+ dx[dir] * s;
            ny = y+ dy[dir] * s;
            
            if( nx >=1 && ny >=1 && nx <= R && ny <= C) break;
            else if ( dir == 1 )    {
                s = s - (x-1);
                x = 1;
                dir = 2;
                
            }
            else if ( dir == 2 )    {
                s = s - (R-x);
                x = R;
                dir =1;
            }
            else if ( dir == 3 )    {
                s = s - (C-y);
                y = C;
                dir = 4;
            }
            else if ( dir == 4 )    {
                s = s- (y-1);
                y =1;
                dir= 3;
            }
            fish[i].d = dir;
            
        }
        
        fish[i].x = nx;
        fish[i].y = ny;
        
        if(visited[nx][ny] != 0)
        {
            int num  = visited[nx][ny];
            
            if( fish[i].z < fish[num].z)    fish[i].die = true;
            else{
                visited[nx][ny]=i;
                fish[num].die = true;
            }
        }
        else    visited[nx][ny]=i;
    }
    
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++)   map[i][j] = visited[i][j];
    }
}

void fishing(int idx)
{
    for(int i=1;i<=R;i++)
    {
        if(map[i][idx] != 0){
            int num= map[i][idx];
            score+=fish[num].z;
            map[i][idx]=0;
            fish[num].die=true;
            return;
        }
    }
}

int main(void)
{
    scanf("%d %d %d",&R,&C,&M);
    
    for(int i=1;i<=M;i++){
        int x,y,s,d,z;
        scanf("%d %d %d %d %d",&x,&y,&s,&d,&z);
        map[x][y]=i;
        fish[i] = {x,y,s,d,z,false};
    }
    
    for(int i=1;i<=C;i++){
        fishing(i);
        move();
    }
    
    printf("%d",score);
    return 0;
    
}