[ 백준 16236 ] 아기 상어 (C++)

백준의 아기상어(16236) 문제이다.

[ 문제 바로가기 ]

삼성전자 S직군 역량테스트 기출문제이다.

[ 문제풀이 ]

1) 문제를 어떻게 접근해야 할지, 사용한 구조체 및 변수들 부터 알아보고 들어가자.

   본인은 먼저 아기상어의 상태를 저장하는 구조체를 하나 만들었다. 구조체에 들어가는 내용으로는

   { 아기상어의 x좌표 , 아기상어의 y좌표 , 아기상어의 크기, 아기상어가 현재 먹은 먹이갯수 , 아기상어가 움직인 시간 }

   이렇게 총 5개의 변수를 구조체에 담아주었다.

   아기상어가 먹이를 먹을 수 있는 좌표들을 찾아가면서, 아기상어의 크기만큼의 먹이를 먹었다면 아기상어의 크기가 증가하고,

   우리는 결과적으로 아기상어가 총 몇초동안 움직였는지를 구해야 하므로, 위의 변수 5개라면 문제를 충분히 풀 수 있다.

   또한, 본인은 먹이를 저장하는 구조체 벡터도 하나 만들어주었다. 문제에서는 먹이를 먹을 수 있는 조건에 대해서 말해주었다.

   조건을 다시한번 확인해보자면....

   1. 먹을 수 있는 물고기가(현재 아기상어의 크기보다 크기가 작은 물고기) 1마리라면 그 물고기를 먹는다.

   2. 먹을 수 있는 물고기가 1마리가 아니라면, 거리가 가장 가까운 물고기를, 그 물고기도 여러마리라면,

     가장 위쪽에 있는 물고기를, 그것마저 같다면 가장 왼쪽에 있는 물고기를 먹는다.

  먹이를 먹을 수 있는 조건이다.

  물고기를 먹을 때, 거리가 굉장히 중요하다. 따라서, 본인은 먹이를 저장하는 구조체를 하나 만들어주었는데, 구조체에 들어가는

  내용으로는 { 물고기의 x좌표, 물고기의 y좌표, 현재 아기상어와 해당 물고기의 거리 } 이렇게 3개의 변수를 관리해주었다.

  현재 아기상어의 상태에서, 먹을 수 있는 물고기들의 정보를 구조체 Vector를 만들어서 저장해 주었다.

  만약, Vector의 Size가 1 이라면 그 물고기를 먹으면 되지만 ,그게 아니라면, Vector를 본인만의 규칙을 만들어서 정렬해주었다.

  더 이상 먹을 수 있는 물고기가 없다면, 즉 Vector의 Size가 0이 되는 시점이라면, 아기상어가 움직인 시간을 출력해주고 프로그램

  을 종료하는 식으로 구현하였다.

  위의 그림은 본인이 위에서 설명한, 아기상어 구조체(왼) 와 물고기의 정보를 저장하는 구조체(오른쪽) 이다.

2) 사용하는 변수 및 구조체들을 알았으니 본격적으로 구체적으로 문제 풀이에 들어가보자.

   먼저, 문제를 구현하는 큰 틀부터 알아보자.

   1. 입력과 동시에 위에서 만들어놓은 상어 구조체에 상어의 정보를 저장한다 !

   2. 먹을 수 있는 물고기가 없을 때 까지, 반복하는 무한루프 속에서, 현재 상어의 좌표에서 BFS를 돌려서 먹을 수 있는

     물고기들을 Vector에 저장한다 !

   3. Vector의 Size가 0이라면 종료 , Vector의 Size가 1이라면, 아기상어의 정보를 수정, Vector의 Size가 2 이상이라면

     본인만의 규칙으로 Vector를 정렬 !

   4. 2~3번을 Vector의 Size가 0이 나올 때 까지 계속해서 반복한다.

  

   1번은 어렵지 않으니 2번부터 알아보자.

   우리는 현재 아기상어에 대한 정보를 구조체에 저장해 놓았다. 구조체를 통해서 아기상어의 x, y 좌표를 가져와서

   현재 아기상어의 좌표를 시작점으로 BFS탐색을 해주었다.

   BFS의 Queue에서는 3개의 변수를 관리해주었다.

   { 현재 x좌표 , 현재 y좌표, 현재까지 움직인 거리 } 이렇게 3개의 변수를 !

    BFS안에서의 내용은 이렇다.

   1. 빈공간이라면 그냥 움직인거리만 ++ 해주고, 방문 !

   2. 아기상어의 크기보다 작은 물고기라면, 작은 물고기에 대한 정보를 Vector에 push해주고, 방문 !

   3. 아기상어의 크기와 같은 물고기라면, 움직인거리만 ++해주고, 방문 !

   4. 아기상어의 크기보다 큰 물고기라면, 접근할 수 없는 곳이므로 방문 X !

   위의 4가지를 구현해주면 된다. 참고로 BFS의 종료조건은 없다. 모든 정점을 방문해보고, 먹을 수 있는 물고기를 모두 탐색해야

   하기 때문이다.

   BFS가 종료된 후에는, Vector의 Size에 따라서 구현 내용이 달라진다.

   우리는, 아기상어가 먹을 수 있는 물고기들만 Vector에 담아주었다. 즉, Vector의 Size가 0이라는 것은 아기상어가 더 이상

   먹을 수 있는 물고기가 존재하지 않는다는 것이다. 따라서 아기상어가 지금까지 움직인 총 시간을 출력해주고, 프로그램을 종료

   한다.

   Vector의 Size가 1이라는 것은, 아기상어가 먹을 수 있는 물고기가 1마리 뿐이라는 것을 의미하고, 아기상어는 무조건 이 물고기

   를 먹으러 가야 한다. 그렇다면, 우리는 아기상어가 이 물고기를 먹으러 가는데 걸리는 시간(가는데 거쳐야 하는 최소칸수)을

   알야한다. 우리는 이를 위해서 먹이 구조체에 "해당 물고기와 아기상어의 거리"를 저장하는 변수도 넣어주었다.

   그렇다면, 아기상어가 먹이를 먹었다는 표시를 어떻게 해야할까?? 아기상어 구조체에 정보를 모두 갱신해주면 된다.

   1. 아기상어의 (x, y)좌표 → 해당 물고기의 (x, y)좌표

   2. 맵에서도 '9'로 표시된 지점 → '0'으로 바꾸고 , 해당 물고기의 좌표를 맵에서도 '9'로 바꾸기 !

   3. 아기상어가 먹은 먹이의 갯수++

   4. 아기상어가 움직인 시간 = 아기상어가 움직인시간 + 해당 물고기한테 가는데 걸리는 시간

      < 누적값이므로, 아기상어가 움직인 시간 = 해당물고기한테 가는데 걸리는 시간  으로 하면 안된다 ! >

   5. 아기상어가 먹은 먹이의 갯수와 아기상어의 크기 비교해서, 크기가 증가될 조건이라면 크기++

   이어서 가자. Vector의 Size가 2 이상이라면 어떻게 처리해줄까?? 위에서, "본인만의 정렬방식으로 Vector를 정렬" 했다고 말했

   다. Vector는 지금 먹이들의 정보를 저장하는 구조체를 저장하는 Vector이고, 구조체에는 3개의 변수값이 있으므로

   순전히, int형 혹은 char형 처럼 STL sort() 함수를 사용하더라도, 원하는대로 정렬되지 않을 것이다.

   따라서, sort(A, B, 본인의기준) 을 사용해주었다.

   여기서 sort함수에 대해서 약간만 알고가자.

   #include<algorithm> 을 사용하면, sort() 라는 함수를 제공받아 사용할 수가 있다.

   sort(A, B)는 A에서 B까지를 오름차순으로 정렬해준다. 즉, 보통 Vector를 정렬한 경우, sort(V.begin(), V.end())로 표현하고는

   한다. 물론, 이경우에는 Vector가 관리하는 자료형이 int형이거나 char형 같이 정렬이 가능한 경우이다.

   하지만 우리는 자료형이 우리가 만든 구조체이다. 이때는 sort(A, B, C)를 사용하자 !

   sort(A, B, C)는 A에서 B까지 C가 true를 return 할 때, 그에 맞게 정렬해준다.

   함수 C는 bool 형으로 이루어져 있으며, 알맞은 2개의 값을 비교해서 원할 때 return true를 해주면 된다.

   우리 같은 경우에는,

   1. 거리비교 → 2. x축비교 → 3. y축비교 를 해줘야 한다. 따라서 아래와 같이 구현하면 된다.

  

위의 설명을 모두 이해했다면, 소스코드를 보면 쉽게 이해할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int Size;
    int Eat_Num;
    int Time;
}Shark;
 
typedef struct
{
    int x;
    int y;
    int Dist;
}Food;
 
int N;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
Shark S;
vector<Food> V;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1 ,-1 ,0 ,0 };
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 9)
            {
                S.x = i;
                S.y = j;
                S.Size = 2;
                S.Eat_Num = 0;
                S.Time = 0;
            }
        }
    }
}
 
void BFS(int a, int b)
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(a, b), 0));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Dist = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (Visit[nx][ny] == false)
                {
                    if (MAP[nx][ny] == 0)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Dist + 1));
                    }
                    else if (MAP[nx][ny] < S.Size)
                    {
                        Food Temp;
                        Temp.x = nx;
                        Temp.y = ny;
                        Temp.Dist = Dist + 1;
 
                        V.push_back(Temp);
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Dist + 1));
                    }
                    else if (MAP[nx][ny] == S.Size)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Dist + 1));
                    }
                }
            }
        }
    }
}
 
bool Sorting_Standard(Food A, Food B)
{
    if (A.Dist <= B.Dist)
    {
        if (A.Dist == B.Dist)
        {
            if (A.x <= B.x)
            {
                if (A.x == B.x)
                {
                    if (A.y < B.y)
                    {
                        return true;
                    }
                    return false;
                }
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
void Solution()
{
    while (1)
    {
        V.clear();
        memset(Visit, false, sizeof(Visit));
 
        BFS(S.x, S.y);
        if (V.size() == 0)
        {
            cout << S.Time << endl;
            break;
        }
        else if (V.size() == 1)
        {
            MAP[V[0].x][V[0].y] = 9;
            MAP[S.x][S.y] = 0;
            S.x = V[0].x;
            S.y = V[0].y;
            S.Eat_Num++;
            S.Time = S.Time + V[0].Dist;
 
            if (S.Eat_Num == S.Size)
            {
                S.Eat_Num = 0;
                S.Size++;
            }
        }
        else
        {
            sort(V.begin(), V.end(), Sorting_Standard);
            MAP[V[0].x][V[0].y] = 9;
            MAP[S.x][S.y] = 0;
            S.x = V[0].x;
            S.y = V[0].y;
            S.Eat_Num++;
            S.Time = S.Time + V[0].Dist;
 
            if (S.Eat_Num == S.Size)
            {
                S.Eat_Num = 0;
                S.Size++;
            }
        }
    }
}
 
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;
}