[ 백준 19237 ] 어른 상어 (C++)

백준의 어른상어(19237) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저 문제를 풀기 전에 '상어' 와 '맵'을 관리하는 부분에 대해서부터 알아보고 문제풀이에 들어가보자.

1. 상어 관리

먼저 상어는 처음에 정해진 '진행방향'을 가지고 있다. 그리고 상어가 움직일 때 마다, 각 상어는 "현재 자신의 진행방향에 따른 우선순위 진행방향"으로 방향을 바꾸면서 움직이게 된다.

그래서 본인은 상어를 관리할 때, 이 정보들을 모두 구조체에 넣어서 관리해 주었다.

struct SHARK
{
    int x;
    int y;
    int Dir;
    bool Live;
    vector<int> Priority[5];
};

위의 코드는 본인인 '상어'를 표현하기 위해서 '상어에 대한 정보들을 구조체로 표현한 코드' 이다.

각 멤버변수들에 대해서 설명을 하자면 (x , y) 는 "현재 상어가 있는 좌표"를 의미한다.

dir 은 "현재 상어의 진행방향"을 의미한다. Live 는 "현재 이 상어가 죽었는지 살았는지"를 나타내준다. true라면 살아있는 상어이고, false라면 다른 상어에게 잡아먹혀서 죽은 상어임을 의미한다.

그리고 마지막 vector배열은 "상어의 진행방향에 따른 우선순위 진행방향"을 저장해 주었다.

각 인덱스에는 4개의 값들이 push될 것이다. 문제에서 이야기 했 듯이, 1 = 위 , 2 = 아래 , 3 = 왼쪽 , 4 = 오른쪽을 의미한다.

즉, Priority[1]에 들어가는 4개의 원소 { a, b, c, d } 는, 현재 상어가 "위쪽을 향하고 있을 때 우선순위 순서대로의 진행방향" 을 의미한다. Priority[2 ~ 4]에는 마찬가지로 상어가 각 방향을 향하고 있을 때 그 다음 진행방향의 우선순위 진행방향들이 순서대로 4개씩 저장되어진다. 위의 구조체를 배열로 만들어서 상어를 구조체배열 형태로 관리해 주었다.

2. 맵 관리

두 번째로는 맵에 대해서 알아보자. 맵에서 관리해 주어야 할 것들에 대해서 부터 생각을 해보자.

1. 특정 좌표에 냄새가 남아있는지 ?

2. 냄새가 남아 있다면 그 냄새는 누구의 것인지 ?

3. 특정 좌표에 상어가 2마리 이상 있는지 ?

본인은 위의 3가지를 맵에서 관리해 주었다. 왜 그런지 지금부터 알아보자.

1. 특정 좌표에 냄새가 남아있는지 ??

- 상어가 움직이기 위해서는, 상어가 움직이려는 좌표에 "다른 상어의 냄새가 없어야만" 해당 좌표로 움직일 수 있다.

  그렇기 때문에, "특정 좌표에 상어의 냄새가 남아있는지"를 알 수 있도록 맵에서 관리해 주었다.

2. 냄새가 남아 있다면 그 냄새는 누구의 것인지 ?

- 상어가 움직이려는 모든 방향을 탐색해 봤을 때도, 더 이상 냄새가 없는 칸이 존재하지 않아서 움직이지 못하는 경우가 있다.

   이 경우에는, "자신의 냄새가 있는 좌표"로 되돌아 가도록 만들어 주어야 한다.

   즉 ! 특정 좌표에 냄새가 남아있는지 없는지도 판단해 주어야 하지만, 그 냄새가 '몇번 상어의 냄새인지' 또한 알 수 있도록,

   그리고 이를 통해서 "갈 수 있는 좌표가 없다면, 자신의 번호가 있는 냄새가 남아있는 좌표로 가도록" 만들어 주었다.  

3. 특정 좌표에 상어가 2마리 이상 있는지 ?

- 상어끼리는 같은 좌표에 존재할 수 없다. 같은 좌표에 존재하게 되면 가장 작은 번호를 가진 상어가 다른 상어들을 모두

   잡아먹게 된다. 즉 ! 상어들이 움직일 때 마다, 맵의 특정 좌표에 2마리 이상의 상어가 존재하는지 판단해주어야 한다.

본인은 위의 3가지를 맵에서 관리해주기 위해서 이 또한 구조체로 만들어 주었다.

struct MAP_INFO
{
    vector<int> V;
    int Smell_Time;
    int Smell_Host;
};

위의 코드가 본인이 맵을 관리하기 위해서 만든 구조체이다.

먼저 Vector는 "해당 좌표에 존재하는 상어의 번호"들이 저장되어 있다. 상어들이 한번 움직이고 난 후에, 특정 좌표에 이 Vector의 크기가 2 이상이라면, 이는 2마리 이상의 상어가 하나의 좌표가 있다는 것이고 조건에 맞게 한 마리의 상어만 남도록 다른 상어들을 죽여야 한다. 'Smell Time'은 냄새가 없어지는 시간을 저장해 놓은 변수이다.

예를 들어서 K = 4 일 때, 1초에, 좌표 (0, 0)에 1번 상어가 냄새를 뿌리고 그 다음 좌표로 움직인 상황을 생각해보자.

그렇게 되면 (0, 0)에 1초에 냄새가 뿌려졌고, K = 4 이므로, 이 냄새는 5초에 없어지게 된다.

Smell_Time 에는 이 '5초'가 저장된다. 즉 ! (0, 0)의 Smell_Time은 '5'이므로, 5초가 될 때까지 다른 상어들은 이 좌표에 올 수 없다라는 것을 의미한다. 그럼 6초에는 ? 6초에는 당연히 다른 상어들이 올 수 있다. 냄새가 지워진 후이기 때문이다.

따라서, "상어가 움직이려는 좌표가 가지고 있는 'Smell_Time' 값이, 현재 시간보다 '작거나 같으면'" 해당 좌표는 이미 냄새가 없어진 후이기 때문에 상어가 움직일 수 있다는 것을 의미한다. 반대로 더 크다면, 아직 다른 상어의 냄새가 남아있는 좌표이기 때문에 그 좌표로는 움직일 수 없다는 것을 의미한다.

위의 설명해서 "작거나 같으면" 움직일 수 있는 이유는, 1초에 뿌려졌을 때, 이 냄새는 '5초에' 사라지기 때문에, '5초'에도 다른 상어가 이 좌표로 올 수 있다.

Smell_Host는 냄새를 뿌리게 되는 순간 해당 냄새를 뿌린 상어의 번호를 저장해준 것이다. 위에서 말했듯이, 상어가 갈 수 있는 칸이 없을 때에는, 이 'Smell Host'값을 보고 "자신이 냄새를 뿌렸던 좌표"를 찾아가게 된다.

3. 구현하기

이제 본격적인 구현으로 들어가보자. 본인은 이 문제를 크게 3가지 과정으로 나눠서 구현하였다.

1. 상어들이 현재 자신의 위치에 냄새 뿌리기

2. 상어들을 움직여 주기

3. 상어들을 죽이기.

이렇게 3가지 과정으로 나누어서 구현하였다.

1. 상어들이 현재 자신의 위치에 냄새 뿌리기

- 냄새를 뿌릴 때에는, 현재 상어가 있는 좌표에 'Smell_Time' 값과 'Smell_Host' 값만 잘 계산해주면 된다.

void Setting_Smell(int Time)
{
    for (int i = 1; i <= M; i++)
    {
        if (Shark[i].Live == false) continue;
 
        int x = Shark[i].x;
        int y = Shark[i].y;
        MAP[x][y].Smell_Time = Time + K;
        MAP[x][y].Smell_Host = i;
    }
}

본인이 구현한 상어가 냄새를 뿌리는 과정을 구현한 함수인데, 인자인 Time은 '현재시간'을 의미한다.

Smell_Time을 보게 되면, 현재시간 + K초가 되고, Smell_Host는 냄새를 뿌린 상어의 번호를 그대로 갖게 된다.

2. 상어들을 움직여 주기

상어들을 움직일 때는 2가지를 생각해주면 된다.

1. 우선순위의 순서대로 진행방향을 설정해서 상/하/좌/우 4칸을 탐색했을 때, 내가 갈 수 있는 칸이 존재하는지 ?

2. 1번과정을 진행했는데, 갈 수 있는 칸이 없다면 ?

이 2가지를 생각해주면 된다. 그래서 본인은, 현재 진행방향의 우선순위에 맞게 4가지 방향을 탐색해줄 때, 혹여나 갈 수 있는 칸이 존재하지 않을 경우, 즉, 2번 경우를 진행하게 될 경우를 대비해서 "내 냄새가 있는 좌표를 찾는 과정"을 진행해 주었다.

void Move_Shark(int Time)
{
    for (int i = 1; i <= M; i++)
    {
        if (Shark[i].Live == false) continue;
        int x = Shark[i].x;
        int y = Shark[i].y;
        MAP[x][y].V.clear();
    }
 
    for (int i = 1; i <= M; i++)
    {
        if (Shark[i].Live == false) continue;
        
        int x = Shark[i].x;
        int y = Shark[i].y;
        int Dir = Shark[i].Dir;
        int Self_x, Self_y, Self_Dir;
        Self_x = Self_y = Self_Dir = -1;
        bool Flag = false;
        
        for (int j = 0; j < Shark[i].Priority[Dir].size(); j++)
        {
            int nDir = Shark[i].Priority[Dir][j];
            int nx = x + dx[nDir];
            int ny = y + dy[nDir];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny].Smell_Time <= Time)
                {
                    Flag = true;
                    MAP[nx][ny].V.push_back(i);
                    Shark[i].x = nx;
                    Shark[i].y = ny;
                    Shark[i].Dir = nDir;
                    break;
                }
                else
                {
                    if (MAP[nx][ny].Smell_Host == i)
                    {
                        if (Self_x == -1)
                        {
                            Self_x = nx;
                            Self_y = ny;
                            Self_Dir = nDir;
                        }
                    }
                }
            }
        }
 
        if (Flag == false)
        {
            MAP[Self_x][Self_y].V.push_back(i);
            Shark[i].x = Self_x;
            Shark[i].y = Self_y;
            Shark[i].Dir = Self_Dir;
        }
    }
}

위의 코드가 상어를 움직여 주는 코드이다. line3 ~8)에서 먼저 기존의 상어에 대한 정보가 저장되어 있는 좌표들을 비워준다.

line22 ~ 51)을 보게 되면, 상/하/좌/우 4방향을 우선순위에 맞게 탐색하면서 갈 수 있는 좌표를 찾는 과정이다. line29 ~ 37)은 그 중에서도, "갈 수 있는 칸이 있는 경우"를 나타낸 것이다. 갈 수 있는 칸이 있다면, 상어의 좌표를 해당 좌표로 옮겨주고 상어의 정보들만 수정해 주면 된다. 또한, line22)에서 보면 맵에서도 해당 좌표에 상어의 번호를 넣어주고 있다.

line38 ~ 51)은 "1번과정에서 갈 수 있는 칸을 찾지 못해서, 2번 과정을 실행해야 할 경우를 대비" 한 코드이다.

즉 ! "갈 수 없는 칸일 때(냄새가 있는 칸일 때), 그 칸의 주인이 나라면, 그 좌표를 저장해 놓는 과정" 을 구현한 코드이다.

line53 ~ 59)는 상어가 움직일 수 없어서, 자기 자신의 냄새가 있는 좌표로 움직이는 과정, 즉 2번 과정을 구현한 것이다.

3. 상어 죽이기

상어를 움직였으니, 어떤 좌표에는 2마리 이상의 상어가 공존하고 있을 수 있다. 이런 경우, 좌표에서 상어를 한 마리만 남아있도록 나머지 상어들을 죽여야 한다.

void Killing_Shark()
{
    for (int i = 1; i <= M; i++)
    {
        if (Shark[i].Live == false) continue;
        
        int x = Shark[i].x;
        int y = Shark[i].y;
        if (MAP[x][y].V.size() >= 2)
        {
            sort(MAP[x][y].V.begin(), MAP[x][y].V.end());
            int Live_Num = MAP[x][y].V[0];
            for (int j = 1; j < MAP[x][y].V.size(); j++)
            {
                int Shark_Num = MAP[x][y].V[j];
                Shark[Shark_Num].Live = false;
            }
            MAP[x][y].V.clear();
            MAP[x][y].V.push_back(Live_Num);
            MAP[x][y].Smell_Host = Live_Num;
        }
    }
}

위의 코드가 본인이 구현한 상어를 죽이는 함수인데, line9)에서 보면 2마리 이상의 상어가 공존할 경우에만 실행된다는 것을 확인할 수 있다. line11)에서, 해당 좌표에 있는 상어들을 "번호 순서대로 오름차순으로 정렬" 시켜주었다. 그렇게 되면 Vector의 0번 Index에 가장 작은 번호를 가진 상어가 있게 된다. 즉, 0번 Index에 저장되어 있는 번호의 상어만이 살아남고 나머지 상어들은 모두 죽게 된다는 것이다. line13 ~ 16)은 나머지 상어들을 죽이는 과정이다.

line18 ~ 20)은 해당 좌표가 다시 한 마리의 상어만 남은 상태가 되었으니 이에 맞도록 좌표의 상태를 재설정 하는 과정이다.

[ 소스코드 ]

#include <iostream>
#include <vector>
#include <algorithm>
 
#define endl "\n"
#define MAX 25
using namespace std;
 
struct SHARK
{
    int x;
    int y;
    int Dir;
    bool Live;
    vector<int> Priority[5];
};
 
struct MAP_INFO
{
    vector<int> V;
    int Smell_Time;
    int Smell_Host;
};
 
int N, M, K;
MAP_INFO MAP[MAX][MAX];
SHARK Shark[410];
 
int dx[] = { 0, -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, -1, 1 }; 
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int a; cin >> a;
            if (a != 0)
            {
                MAP[i][j].V.push_back(a);
                Shark[a].x = i;
                Shark[a].y = j;
            }
            MAP[i][j].Smell_Time = 0;
            MAP[i][j].Smell_Host = 0;
        }
    }
    for (int i = 1; i <= M; i++)
    {
        int Dir; cin >> Dir;
        Shark[i].Dir = Dir;
        Shark[i].Live = true;
    }
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            int Arr[4];
            cin >> Arr[0] >> Arr[1] >> Arr[2] >> Arr[3];
            for (int k = 0; k < 4; k++)
            {
                Shark[i].Priority[j].push_back(Arr[k]);
            }
        }
    }
}
 
bool Check()
{
    for (int i = 2; i <= M; i++)
    {
        if (Shark[i].Live == true) return false;
    }
    return true;
}
 
void Setting_Smell(int Time)
{
    for (int i = 1; i <= M; i++)
    {
        if (Shark[i].Live == false) continue;
 
        int x = Shark[i].x;
        int y = Shark[i].y;
        MAP[x][y].Smell_Time = Time + K;
        MAP[x][y].Smell_Host = i;
    }
}
 
void Move_Shark(int Time)
{
    for (int i = 1; i <= M; i++)
    {
        if (Shark[i].Live == false) continue;
        int x = Shark[i].x;
        int y = Shark[i].y;
        MAP[x][y].V.clear();
    }
 
    for (int i = 1; i <= M; i++)
    {
        if (Shark[i].Live == false) continue;
        
        int x = Shark[i].x;
        int y = Shark[i].y;
        int Dir = Shark[i].Dir;
        int Self_x, Self_y, Self_Dir;
        Self_x = Self_y = Self_Dir = -1;
        bool Flag = false;
        
        for (int j = 0; j < Shark[i].Priority[Dir].size(); j++)
        {
            int nDir = Shark[i].Priority[Dir][j];
            int nx = x + dx[nDir];
            int ny = y + dy[nDir];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny].Smell_Time <= Time)
                {
                    Flag = true;
                    MAP[nx][ny].V.push_back(i);
                    Shark[i].x = nx;
                    Shark[i].y = ny;
                    Shark[i].Dir = nDir;
                    break;
                }
                else
                {
                    if (MAP[nx][ny].Smell_Host == i)
                    {
                        if (Self_x == -1)
                        {
                            Self_x = nx;
                            Self_y = ny;
                            Self_Dir = nDir;
                        }
                    }
                }
            }
        }
 
        if (Flag == false)
        {
            MAP[Self_x][Self_y].V.push_back(i);
            Shark[i].x = Self_x;
            Shark[i].y = Self_y;
            Shark[i].Dir = Self_Dir;
        }
    }
}
 
void Killing_Shark()
{
    for (int i = 1; i <= M; i++)
    {
        if (Shark[i].Live == false) continue;
        
        int x = Shark[i].x;
        int y = Shark[i].y;
        if (MAP[x][y].V.size() >= 2)
        {
            sort(MAP[x][y].V.begin(), MAP[x][y].V.end());
            int Live_Num = MAP[x][y].V[0];
            for (int j = 1; j < MAP[x][y].V.size(); j++)
            {
                int Shark_Num = MAP[x][y].V[j];
                Shark[Shark_Num].Live = false;
            }
            MAP[x][y].V.clear();
            MAP[x][y].V.push_back(Live_Num);
            MAP[x][y].Smell_Host = Live_Num;
        }
    }
}
 
void Solution()
{
    for (int Time = 0; Time < 1001; Time++)
    {
        if (Check() == true)
        {
            cout << Time << endl;
            return;
        }
        Setting_Smell(Time);
        Move_Shark(Time);
        Killing_Shark();
    }
    cout << -1 << 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;
}