[BOJ] - 17143. 낚시왕

[URL]

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

17143번: 낚시왕

 

[풀이 과정]

시뮬레이션 문제

 

input()을 통하여 입력받고 입력받은 값을 벡터에 저장

이 후 king(낚시왕)은 총 C번 만큼 이동하면서 상어를 잡는다.

 

크게 3단계로 나누어 진행 

1. mapUpdate() + king 오른쪽으로 한 칸 이동

2. king 상어 잡는다 -> kingCatchShark();

3. 상어 이동 -> sharkMove();

 

1. mapUpdate()

이중 for문 동안 0으로 초기화

벡터 크기 만큼 돌며 해당 좌표값++;

이후 map[][] == 1 인곳 상어 잡는데 사용하기 위함!!

king의 이동은 y좌표값 1씩 증가

 

2.king 상어 잡는다 -> kingCatchShark()

king의 위치로부터 R만큼 수직으로 내려오면서 map 검사

map[][] != 0 인 경우 상어 있다고 판단하여

상어 잡는다 -> dap에 잡은 상어의 크기만큼 더해준다.

 

3. 상어 이동 -> sharkMove();

이 부분이 가장 시간 잡아먹은 부분.......

 

우선 벡터의 크기만큼 for문

-> 여기서 현재의 cx, cy를 구한다.

 

각 벡터의 속도만큼 for문

-> 여기서는 한칸씩 이동하는 nx, ny

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

활용하여 한칸 씩 이동하게 하였으며 방향 1,2를 묶고, 3,4를 묶어서 생각함

한칸 씩 이동하며, 범위값을 벗어나는 경우만 방향 바꿔주고, 위치값 설정

 

이후 같은 좌표에 size가 큰 상어가 앞으로 오게 정렬

 

같은 좌표에서 size제일 큰 놈 빼고 다 삭제 (상어가 나머지 잡아먹음) --> 이 때, 벡터사이즈가 0인경우 에러 발생 주의!!

 

[소스 코드]

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int R, C, M;
int map[105][105];
int dap = 0;
 
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, 1, -1 };
 
struct King {
    int x;
    int y;
};
King king;
 
 
struct Shark {
    int x;
    int y;
    int s;    // 속력
    int d;    // 이동 방향
    int z;    // 크기
};
vector <Shark> V;
 
bool cmp(Shark a, Shark b) {
    if (a.x == b.x)
    {
        if (a.y == b.y)
            return a.z > b.z;
        else
            return a.y < b.y;
    }
    else
        return a.x < b.x;
}
 
void input() {
    scanf("%d %d %d", &R, &C, &M);
 
    for (int i = 0; i < M; i++)
    {
        Shark temp;
        scanf("%d %d %d %d %d", &temp.x, &temp.y, &temp.s, &temp.d, &temp.z);
        V.push_back(temp);
    }
}
 
void updateMap() {
 
    for (int i = 1; i <= R; i++)
    {
        for (int j = 1; j <= C; j++)
        {
            map[i][j] = 0;
        }
    }
 
    for (int i = 0; i < V.size(); i++)
    {
        map[V[i].x][V[i].y]++;
    }
}
 
void kingCatchShark() {
 
    for (int i = 1; i <= R; i++)
    {
        if (map[i][king.y] != 0)
        {
            //상어 벡터에서 x,y에 해당하는 상어를 삭제해야한다.
            for (int k = 0; k < V.size();)
            {
                if (V[k].x == i && V[k].y == king.y)
                {
                    dap += V[k].z;
                    V.erase(V.begin() + k);
                }
                else
                {
                    k++;
                }
            }
 
            break;
        }
    }
}
 
void sharkMove() {
    for (int k = 0; k < V.size(); k++)
    {
        int cx = V[k].x;
        int cy = V[k].y;
        int dir = V[k].d;
        int speed = V[k].s;
 
        for (int i = 0; i < speed; i++)
        {
            if (dir == 1 || dir == 2)
            {
                int nx = cx + dx[dir];
                int ny = cy + dy[dir];
 
                if (nx < 1)
                {
                    dir = 2;
                    nx = nx + 2;
                }
 
                if (nx > R)
                {
                    dir = 1;
                    nx = nx - 2;
                }
 
                cx = nx;
                cy = ny;
            }
 
            else if (dir == 3 || dir == 4)
            {
                int nx = cx + dx[dir];
                int ny = cy + dy[dir];
 
                if (ny > C)
                {
                    dir = 4;
                    ny = ny - 2;
                }
 
                if (ny < 1)
                {
                    dir = 3;
                    ny = ny + 2;
                }
 
                cx = nx;
                cy = ny;
            }
        }
 
        V[k].x = cx;
        V[k].y = cy;
        V[k].d = dir;
    }
 
    // 같은 좌표에 size제일 큰 상어뺴고 나머지 삭제
    sort(V.begin(), V.begin() + V.size(), cmp);
 
    // 이 부분 항상 조심!! , 벡터사이즈 0인 경우 ERROR발생!!!
    if (V.size() != 0)
    {
        for (int i = 0; i < V.size() - 1; )
        {
            if (V[i].x == V[i + 1].x && V[i].y == V[i + 1].y)
            {
                V.erase(V.begin() + i + 1);
            }
            else
            {
                i++;
            }
        }
    }
}
 
 
int main() {
 
    king.x = 0;
    king.y = 0;
 
    input();
 
    for (int c = 0; c < C; c++)    // 낚시왕이 총 이동하는 횟수: C
    {
        //map Update
        updateMap();
 
        //1) king 옆으로 한칸 이동
        king.y++;
 
        //2) king 상어 잡는다
        kingCatchShark();
 
        //3) 상어 이동
        sharkMove();
    }
 
    printf("%d\n", dap);
 
    return 0;
}