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

백준의 낚시왕(17143) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 문제를 풀기 전에 변수를 어떤 자료형으로 선언했는지부터 알아보고, 그 자료형을 선택한 이유와 어떻게 사용되는지

    부터 알아본 후에 문제를 풀어보자.

   

    먼저 본인은 상어들의 정보를 한번에 관리하기 위해서 구조체를 하나 만들어 주었다. 구조체에서 관리해주는 변수로는

    { 상어의(x,y)좌표 , 상어의 속력 , 상어의 진행방향 , 상어의 크기 , 상어의 번호 }

    이렇게 총 6개의 자료를 관리해 주었다.

    또한, 상어들의 정보를 모두 저장해줄 vector를 하나 생성해서 저장해 주었다.

    또 하나는 2차원 맵을 int형이 아닌 vector<int> 형으로 생성해 주었다. 이렇게 만들어준 이유는 해당좌표에 존재하는

    상어의 번호(구조체에서 '상어의 번호')를 저장해 주기 위함이었다.

    중간에 보면 상어가 서로 같은 정점에서 만나게 될 경우 더 큰 상어가 작은 상어를 잡아 먹는다는 부분이 있다.

    즉, MAP[x][y]의 Size가 2이상일 경우, 특정 기준으로 정렬을 통해서 더 큰 상어만이 살아남도록 구현해 주었다.

    자세한건 밑에서 구체적으로 알아보도록 하자.

2) 먼저 문제의 진행방식을 크게 3단계로 나눌 수 있다.

    1. 사람이 낚시하기

    2. 상어 움직이기

    3. 움직인 상어들 중에서 서로 겹치는 상어를 죽여주기.

    단계별로 알아보도록 하자.

    먼저 사람이 낚시를 하는 과정이다.

    낚시를 할 때에는 현재 열이 몇 열인지만 알고 있으면 된다. 현재 열의 1행부터 ~ R행까지 진행하면서 MAP의 Size가

    1인 정점을 만나게 되면, 그 상어를 죽여주고 상어의 Size를 더해주면 된다.

    그런데, MAP의 Size가 1이라는 것은 상어가 그 좌표에 존재한다는 것은 알겠는데, 그 상어가 어떤 상어인지 어떻게 알까?

    이를 위해서 MAP을 vector<int> 형으로 선언해 준 것이다. 위에서도 말했듯이, MAP에는 해당 좌표에 존재하는 상어의

    번호가 원소로 들어가 있다.

    즉 예를들어서 MAP[x][y]의 vector 상태가 { 0 } 이라면, 0번 상어가 해당 좌표에 존재한다는 것이다.

    우리는 이를 통해서 해당 상어를 죽여줄 수 있다. 죽이는 과정은 간단하다.

    해당 상어의 크기를 0으로 만들어 주었다.

    두번쨰로는 상어가 움직이는 과정이다.

    이 과정은 사실 수 많은 방법이 존재할 수 있지만, 본인은 정말 가장 간단하게 한칸한칸씩 움직여 주었다.

    맵의 범위를 벗어날 때 마다 적절하게 값을 변경해 주면서 방향을 바꿔주었다.

    여기서 주의해야할 것은, 상어를 모두 움직였다면 MAP에서도 바꿔주어야 하고, 해당 상어의 (x, y)와 진행방향 또한

    바꿔줘야 한다는 것을 주의해주자.

    사실 처음에 이렇게 구현을 해서 pass를 받았으나, 재채점 이 후 시간초과가 나서 이 부분을 수정해보았다.

    문제의 제한시간이 1초인데, 최악의 경우 최대 상어수가 10000마리인데, 10000마리가 1000의 스피드, 즉 1000칸씩

    움직이게 될 경우 10000 * 1000 = 10^7 만큼의 시간이 걸리고, 사람이 1열부터 C열까지 움직일 때 마다 해야 하니

    10^7 * 10^2(C의 최대값) 이 되어 최악의 경우 10^9만큼의 연산을 하게 된다.

    당연히 제한시간 1초 내에 해결될 수가 없다.

    따라서 이 부분을 정말 간단하게 모듈러 연산으로 한번 바꿔보았다. 이 부분에 대해서 알아보자.

    하나의 상어가, 자신의 원래 방향을 그대로 유지한채 자기 자리로 돌아오기 위해서는 몇 칸이 필요할까 ?

    답부터 말하자면, "위아래로 움직이는 상어의 경우 : (R-1)*2 , 좌우로 움직이는 상어의 경우 : (C-1)*2" 가 된다.

   

    정말 간단하게 상어의 진행방향과 번호만 나타낸 것이다. 맵의 R = 4, C = 5 이다. 맵의 가장 왼쪽 위를 (1,1)로 생각하겠다.

    먼저, 1번 2번 상어를 보자. 1번 상어가 진행방향을 오른쪽으로 가지고 다시 (2, 1)로 돌아오기 위해서는 몇 칸을 움직여

    주어야 할까? 직접 하나하나 세보면 알겠지만 8칸을 움직이면 된다. 방향이 반대일 때 제자리에 도착하지만, 어차피

    이 다음에 움직일 때 바로 방향이 전환되기 때문에 상관이 없다.

    2번 상어의 경우는 ?? 4번 움직이게 되면, 똑같은 자리에 진행방향 반대일 것이고, 8번 움직이면, 처음과 똑같은 자리에

    같은 진행방향을 가진 채로 도착하게 된다. 즉, 좌우로 움직이는 상어들에 경우 (C - 1) * 2번을 움직이게 되면

    처음 자리에 같은 진행방향을 가진 채 도착을 하게 된다.

    3번, 4번의 경우도 똑같다. (R - 1) * 2번을 움직이게 되면 처음 자리에 같은 진행방향을 가진 채 도착하게 된다.

   

    그렇다면 ! 위의 그림에서 2번상어가 9칸을 움직일 수 있다면 어디에 가있게 될까? 아마 한칸 왼쪽칸인 (3, 2)에 위치하게

    될 것이다. 이거를 굳이, 9칸을 움직여 볼 필요가 없다. 왜 ? 우리는 8칸을 움직이면 처음과 같은 상태라는 것을 알기 때문

    이다. 즉, 9 % 8 한 칸 만큼만 움직여 주면 된다. 그럼 20칸을 움직이게되면 ? 20 % 8 = 4가 되고, 4칸만 움직여 주게 되면

    20칸을 움직인 것과 똑같은 결과를 가져오게 된다. 본인은 이렇게 모듈러 연산을 통해서 최대 (R - 1) * 2칸 혹은

    (C - 1) * 2칸만 움직이도록 구현해 주었다.

    이 부분을 이렇게 수정하니 시간초과를 받지 않고 pass를 받을 수 있었다.   

  

    세번째로는 상어가 서로 잡아먹는 과정이다.

    우리는 상어가 서로 같은칸에 있음을 어떻게 알 수 있을까?? 아마 해당 칸의 MAP의 Size가 2 이상일 것이다.

    즉, 2이상인 정점에 대해서는 본인은 상어의 크기순으로 정렬을 해 주었다.

    정렬을 하게 되면 0번째 Index에 크기가 가장 큰 상어가 존재할 것이고 그 이후에 점차 작아지는 순으로 정렬이 되어

    있을 것이다. 이후에, 0번째 Index를 제외한 모든 상어의 상태를 false로 바꿔주고 MAP을 비운 후에 0번째 Index에

    존재하는 상어의 번호만 다시 해당 좌표에 넣어주면 된다.

3) 문제를 있는 그대로 구현을 하다보면 어렵지 않게 해결할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 100 + 1
using namespace std;
 
struct Shark_Info
{
    int R;
    int C;
    int Speed;
    int Direct;
    int Size;
    int Num;
};
 
int R, C, M, Answer;
vector<int> MAP[MAX][MAX];
vector<Shark_Info> Shark;
 
int dx[] = { 0, -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, 1, -1 };
 
bool Standard(int A, int B)
{
    if (Shark[A].Size > Shark[B].Size) return true;
    return false;
}
 
void Input()
{
    cin >> R >> C >> M;
    for (int i = 0; i < M; i++)
    {
        int r, c, s, d, z;
        cin >> r >> c >> s >> d >> z;
        Shark.push_back({ r,c,s,d,z,i });
        MAP[r][c].push_back(i);
    }
}
 
bool Check()
{
    for (int i = 0; i < Shark.size(); i++)
    {
        if (Shark[i].Size != 0) return false;
    }
    return true;
}
 
void Fishing(int Idx)
{
    for (int i = 1; i <= R; i++)
    {
        if (MAP[i][Idx].size() != 0)
        {
            Answer = Answer + Shark[MAP[i][Idx][0]].Size;
            Shark[MAP[i][Idx][0]].Size = 0;
            MAP[i][Idx].clear();
            break;
        }
    }
}
 
void Move_Shark()
{
    for (int i = 0; i < Shark.size(); i++)
    {
        if (Shark[i].Size == 0) continue;
        int x = Shark[i].R;
        int y = Shark[i].C;
        MAP[x][y].clear();
    }
 
    for (int i = 0; i < Shark.size(); i++)
    {
        if (Shark[i].Size == 0) continue;
        int x = Shark[i].R;
        int y = Shark[i].C;
        int Direct = Shark[i].Direct;
        int Speed = Shark[i].Speed;
 
        if (Direct == 1 || Direct == 2)
        {
            int Rotate = (R - 1) * 2;
            if (Speed >= Rotate) Speed = Speed % Rotate;
 
            for (int j = 0; j < Speed; j++)
            {
                int nx = x + dx[Direct];
                int ny = y + dy[Direct];
                if (nx < 1)
                {
                    Direct = 2;
                    nx = nx + 2;
                }
                if (nx > R)
                {
                    Direct = 1;
                    nx = nx - 2;
                }
                x = nx;
                y = ny;
            }
        }
        else
        {
            int Rotate = (C - 1) * 2;
            if (Speed >= Rotate) Speed = Speed % Rotate;
 
            for (int j = 0; j < Speed; j++)
            {
                int nx = x + dx[Direct];
                int ny = y + dy[Direct];
                if (ny < 1)
                {
                    Direct = 3;
                    ny = ny + 2;
                }
                if (ny > C)
                {
                    Direct = 4;
                    ny = ny - 2;
                }
                x = nx;
                y = ny;
            }
        }
        
        Shark[i].R = x;
        Shark[i].C = y;
        Shark[i].Direct = Direct;
        MAP[x][y].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() > 1)
            {
                sort(MAP[i][j].begin(), MAP[i][j].end(), Standard);
                int Live_Index = MAP[i][j][0];
                for (int k = 1; k < MAP[i][j].size(); k++)
                {
                    Shark[MAP[i][j][k]].Size = 0;
                    Shark[MAP[i][j][k]].R = -1;
                    Shark[MAP[i][j][k]].C = -1;
                }
                MAP[i][j].clear();
                MAP[i][j].push_back(Shark[Live_Index].Num);
            }
        }
    }
}
 
void Solution()
{
    if (M == 0)
    {
        cout << 0 << endl;
        return;
    }
    for (int i = 1; i <= C; i++)
    {
        if (Check() == true) break;
        Fishing(i);
        Move_Shark();
        Kill_Shark();
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}