[ 백준 19236 ] 청소년 상어 (C++)

백준의 청소년 상어(19236) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

상어가 먹을 수 있는 물고기 번호의 합의 최대값을 구해야 하는 문제이다.

먼저 어떻게 접근하면 좋을지 생각을 해보자.

가장 먼저, '물고기'에 대해서 생각을 해보자. 초기에 물고기는 총 16마리(4 x 4)가 존재하고 각각 고유한 방향을 가지고 있다.

그리고 '물고기가 움직이는 과정'에서 그 방향이 바뀔 수도 있다. 그래서 본인은 '물고기'에 대한 정보를 관리하기 위해서 구조체를

하나 만들어 주었다.

struct FISH
{
    int x;
    int y;
    int Dir;
    bool Live;
};

바로 위의 구조체이다. 물고기들은 자신의 좌표(x, y)를 가지고 있으며, 진행 방향(Dir)을 가지고 있다. 그리고 상어에게 잡아 먹힐 수도 있기 때문에 이미 잡아먹혀서 없는 물고기는 Live = false로, 살아있는 물고기는 Live = true 로 관리해 주었다.

그리고 전체적인 맵은 int형 2차원 배열로 만들어 주었는데, '-1'은 현재 상어가 있는 칸, '0'은 빈 칸(상어도 물고기도 없는 칸), 나머지 숫자들은 물고기들의 번호를 넣어줌으로써 맵을 관리해주었다.

그럼 지금부터는 보다 구체적인 구현 내용으로 들어가보자.

상어는 가장 처음에 (0, 0)좌표에 있는 물고기를 먹고 시작한다. 그리고 (0, 0)에 있었던 물고기의 방향을 상어가 가지게 된다.

그리고 물고기들이 움직인 후에, 상어는 현재 상어의 방향 중에서 "움직일 수 있는 칸" 중에서 하나의 칸으로 움직이게 된다.

위의 과정이 계속해서 반복되는 형태이다.

상어가 움직일 수 있는 칸 중에서 하나의 칸으로 움직일 수 있기 때문에, 상어의 움직임에 의해서 여러가지 경우의 수가 발생할 수 있다. 물론, 이 여러가지 경우의 수 중에서 상어가 먹은 물고기 번호의 합의 최댓값을 구해야 하는 것이다.

그래서 ! 본인은 이 부분을 모든 경우를 탐색해보는 완전탐색, 완전탐색 중에서도 '깊이 우선 탐색(DFS)' 방법으로 접근해 보았다.

본인은 DFS함수 안에서 크게 2가지 내용을 구현하였다.

첫 번째로는 물고기들이 움직이는 과정을 두 번째로는 상어가 움직이는 과정을 구현하였다.

이 때, 주의해줘야 할 부분을 생각해보자.

1. 맵의 변화

- 본인은, DFS함수가 한번 실행될 때 마다 가장 먼저 "물고기들을 움직여주는 과정" 을 진행해주었고, 그 이후에 "상어를 움직여주

   는 과정"을 진행해주었다. 그런데 ! 이렇게 구현할 때 생각해줘야 할 것이 맵을 다시 이전의 상태로 되돌려 놓는 과정이다.

   DFS는 재귀를 통해서 진행되기 때문에, 하나의 경우를 체크하고 그 다음 경우를 체크하기 위해서 실행했던 내용을 취소함으로써

   되돌려 놓는 과정이 필요하다. 이 문제 역시나 그렇다. 맵을 다시 이전의 상태로 되돌려 놓는 것이 굉장히 중요하다.

   특히, 물고기가 움직여주고, 상어가 움직여주는 과정에 의해서 경우에 따라 맵이 완전히 달라져 버리기 때문에 반드시 이 과정이

   중요하다.

2. 물고기의 상태 변화

- DFS함수 안에서 물고기들을 움직여고, 상어가 움직여주는 과정을 진행했다고 이야기했다. 그런데 ! 상어는 "움직일 수 있는

  여러개의 칸 중에서 하나의 칸을 선택"해서 움직이게 된다. 즉 ! 상어가 어떤 물고기를 먹는지에 따라서 물고기의 상태가

  달라질 수 있다 라는 것이다. 어떤 경우에는 a번 물고기가 먹혔는데, 그 다음 경우에는 b번 물고기가 먹힐 수 있다 라는 것이다.

  즉 ! 이런 경우 경우 마다 어떤 물고기가 먹혔는지, 다른 물고기를 먹으러 가게 될 경우 이전 경우에서 먹혔던 물고기의 상태를

  다시 되돌려 주는 과정이 필요하다.

본인은 DFS함수에서 총 4개의 인자를 가지고 함수를 관리해주었다.

바로 { 상어의 현재 x좌표 , 상어의 현재 y좌표 , 상어의 현재 진행방향 , 현재까지 먹은 물고기 번호의 합 }

이렇게 4개의 인자를 관리해주었다. 위에서 했던 이야기를 본인이 코드로 구현한 DFS함수이다.

void DFS(int x, int y, int Dir, int Sum)
{
    Answer = Max(Answer, Sum);
    int C_MAP[4][4];
    FISH C_Fish[20];
    Copy_State(C_MAP, MAP, C_Fish, Fish);
    Move_Fish();
 
    for (int i = 1; i <= 3; i++)
    {
        int nx = x + dx[Dir] * i;
        int ny = y + dy[Dir] * i;
        if (nx >= 0 && ny >= 0 && nx < 4 && ny < 4)
        {
            if (MAP[nx][ny] == 0) continue;
            
            int Fish_Num = MAP[nx][ny];
            int nDir = Fish[Fish_Num].Dir;
 
            Make_State(x, y, nx, ny, Fish_Num, true);
            DFS(nx, ny, nDir, Sum + Fish_Num);
            Make_State(x, y, nx, ny, Fish_Num, false);
        }
        else break;
    }
 
    Copy_State(MAP, C_MAP, Fish, C_Fish);
}

먼저 간단하게 변수들에 대해서만 설명을 하자면, 'MAP'은 원본의 맵을, 'Fish'는 원본의 물고기 상태를 저장해놓은 구조체 배열을

의미한다.

line4 ~ 5)에서 보게 되면, "현재의 맵 상태와 , 물고기의 상태를 임시 저장해주기 위한 변수" 들을 선언해 주었다.

line6)에서 보면, "현재의 맵 상태와, 현재의 물고기 상태를 line 4 ~ 5)에서 선언해준 임시 변수들에 저장해 주고 있다.

line7)에서 보면 물고기들을 움직이는 과정을 진행해 주고 있다. (이 부분은 아래쪽에서 구체적으로 설명하겠다.)

line9 ~ 25)를 보게 되면 "상어의 움직임"을 나타내는 과정이다. 맵이 애초에 4 x 4 로 고정되어 있기 때문에, 상어는 어느 위치에

있든, 어느 방향으로 향하고 있든 최대 3번까지 밖에 움직일 수가 없다. 따라서 line9)에서 보면 3칸까지만 움직이도록 설정해준 것이다. line 17 ~ 22)를 보게 되면, "상어가 움직일 수 있는 칸을 찾았을 때"를 구현한 것이다. 즉 ! 현재 좌표에서 현재 진행방향으로

움직였을 때, 물고기가 있는 칸을 찾았을 때를 구현한 것이다. 물고기가 있는 칸을 찾았으면, 해당 물고기를 먹었다는 것을 표시해주고, 상어의 좌표를 움직여 주어야 한다. 이 과정을 line20) 에서 진행해주고 있다. 그리고 나서는 물고기를 먹은 좌표와 먹은 물고기의 진행방향을 가지고 line21) 에서 DFS를 호출하게 된다.

line22)에서는 탐색을 끝나고 다시 돌아온 경우이다. 위에서 말했듯이 먹은 물고기를 다시 먹지 않은 것 처럼 취소하고, 상어의 좌표를 원래의 좌표로 옮겨주는 과정이 필요하다. 이 과정을 line22)에서 진행해 주고 있는 것이다.

Make_State()라는 함수는 다음과 같이 구현해 보았다.

void Make_State(int x, int y, int nx, int ny, int Fish_Num, bool T)
{
    if (T == true)
    {
        MAP[x][y] = 0;
        MAP[nx][ny] = -1;
        Fish[Fish_Num].Live = false;
    }
    else
    {
        MAP[x][y] = -1;
        MAP[nx][ny] = Fish_Num;
        Fish[Fish_Num].Live = true;
    }
}

인자로 설정되어 있는 (x, y)는 '현재 상어의 위치'를, (nx, ny)는 '상어가 움직일 위치'를, Fish_Num은 '상어가 먹으려는 물고기의 번호'를, 그리고 상태를 바꾸고 다시 되돌리는 것은 'T'라는 bool형 변수로 구분해 주었다.

line3 ~ 8)은 "상어가 (x, y)에서 (nx, ny)로 움직임으로써, 'Fish_Num'번 물고기를 먹겠습니다" 라는 것을 표현한 것이다.

가장 처음에 말했듯이, 맵에서 상어가 있는 칸은 '-1'로, 빈 칸은 '0'으로, 물고기가 있는 칸은 물고기의 번호로 표현해 주었다.

즉, (x, y)에서 (nx, ny)로 상어가 움직이는 것이기 때문에, (x, y)는 빈 칸이 되고, (nx, ny)에는 상어가 있는 위치가 된다.

그리고, Fish_Num번 물고기는 죽은 걸로 체크를 해 주었다.

반대로 line9 ~ 14)는 이 과정을 되돌려 주는 것이다. (x, y)는 다시 상어가 있는 칸이 되므로 '-1'로, (nx, ny)는 Fish_Num번 물고기가 있었던 칸이므로, Fish_Num으로, Fish_Num번 물고기는 다시 살아있는 걸로 체크해 주었다.

그리고 다시 위의 DFS함수를 보게 되면 마지막 line 27)에 맵의 상태를 되돌리는 과정이 있다. 이 과정은 line7)에서 물고기를 움직여 주었기 때문에, 그로 인해서 물고기들의 좌표들이 바뀌었기 때문에 이를 다시 되돌리는 과정을 진행한 것이다.

어떻게 ? 기존에 "현재 상태를 임의로 저장해 두었던 line4~5)에 선언해 놓은 임시 변수들"을 통해서 되돌려 놓은 것이다.

그럼 지금부터는 물고기를 움직이는 과정을 한번 알아보자. (이 부분은 본인이 가장 편하신 방법대로 하시는 것을 추천드립니다.)

물고기가 움직일 수 있는 조건은 다음과 같다.

1. 움직이려는 좌표가 맵의 범위 내에 존재하는 좌표인지

2. 1번 조건을 만족한다면, 그 좌표는 빈 칸이거나 다른 물고기가 있는 칸인지(= 상어가 없는 칸인지)

이렇게 2가지 조건이 있다. 그리고 위의 조건을 만족하지 않는다면, 반시계 방향으로 45도씩 방향을 바꾼다고 되어있다.

그리고 문제에서 제시한 방향인 1 ~ 8을 그림으로 나타내면 다음과 같다.

.

방향이 위와 같이 설정되어 있다. 즉 ! 반시계 방향으로 45도씩 바꾼다는 것은 "현재 진행방향 + 1을 한 방향으로 바꾸겠습니다" 라는 것을 의미한다. 물론 ! (현재 진행방향 + 1 == 9) 인 경우에는 다시 '1'로 바꿔줘야 한다.

그래서 본인은 크게 2가지로 나눠서 물고기를 움직여 주었다.

1. 물고기가 현재 진행방향으로 움직일 수 있는지 판단하기.

만약 이 1번 과정에서 움직일 수 있다면 그대로 물고기를 옮겨주거나, 물고기들 끼리 좌표를 바꿔주면 된다.

2. 1번 조건으로 움직일 수 없다면, 나머지 7방향을 탐색해보기.

1번 과정에서 움직일 수 없다면, 나머지 7방향을 탐색해 보면 된다. 물론 이 경우에도 움직일 수 있는 칸이 없을 수도 있다.

그럼 움직여주지 않으면 된다.

[ 소스코드 ]

#include <iostream>
#include <algorithm>
#include <queue>
 
#define endl "\n"
#define MAX 4
using namespace std;
 
struct FISH
{
    int x;
    int y;
    int Dir;
    bool Live;
};
 
int Answer;
int MAP[MAX][MAX];
FISH Fish[20];
 
int dx[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int a, b; cin >> a >> b;
            MAP[i][j] = a;
            Fish[a] = { i, j, b, true };
        }
    }
} 
 
void Copy_State(int A[][4], int B[][4], FISH C[], FISH D[])
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            A[i][j] = B[i][j];
        }
    }
    for (int i = 1; i <= 16; i++) C[i] = D[i];
}
 
void Swap_Fish(int Idx, int IIdx)
{
    /* 물고기들 끼리 자리를 바꾸는 경우 물고기들의 좌표를 바꿔주는 함수. */
    FISH Temp = Fish[Idx];
    Fish[Idx].x = Fish[IIdx].x;
    Fish[Idx].y = Fish[IIdx].y;
    Fish[IIdx].x = Temp.x;
    Fish[IIdx].y = Temp.y;
}
 
void Move_Fish()
{
    /* 물고기의 움직임을 나타내는 함수. */
    for (int i = 1; i <= 16; i++)
    {
        if (Fish[i].Live == false) continue;
 
        int x = Fish[i].x;
        int y = Fish[i].y;
        int Dir = Fish[i].Dir;
        
        int nx = x + dx[Dir];
        int ny = y + dy[Dir];
        bool Flag = false;
        if (nx >= 0 && ny >= 0 && nx < 4 && ny < 4)
        {
            if (MAP[nx][ny] == 0)
            {
                Flag = true;
                Fish[i].x = nx;
                Fish[i].y = ny;
                MAP[nx][ny] = i;
                MAP[x][y] = 0;
            }
            else if(MAP[nx][ny] != -1)
            {
                Flag = true;
                Swap_Fish(i, MAP[nx][ny]);
                swap(MAP[x][y], MAP[nx][ny]);
            }
        }
 
        /* 여기까지 왔는데 Flag = false 라는 것은,
         * 물고기가 현재 진행방향으로는 움직일 수 없다는 것을 의미. */
        /* 다른 7방향을 탐색해본다. */
        if (Flag == false)
        {
            int nDir = Dir + 1;
            if (nDir == 9) nDir = 1;
            int nx = x + dx[nDir];
            int ny = y + dy[nDir];
 
            while (nDir != Dir)
            {
                if (nx >= 0 && ny >= 0 && nx < 4 && ny < 4)
                {
                    if (MAP[nx][ny] == 0)
                    {
                        Fish[i].x = nx;
                        Fish[i].y = ny;
                        MAP[nx][ny] = i;
                        MAP[x][y] = 0;
                        Fish[i].Dir = nDir;
                        break;
                    }
                    else if (MAP[nx][ny] != -1)
                    {
                        Swap_Fish(i, MAP[nx][ny]);
                        swap(MAP[x][y], MAP[nx][ny]);
                        Fish[i].Dir = nDir;
                        break;
                    }
                }
                nDir++;
                if (nDir == 9) nDir = 1;
                nx = x + dx[nDir];
                ny = y + dy[nDir];
            }
        }
    }
}
 
void Make_State(int x, int y, int nx, int ny, int Fish_Num, bool T)
{
    /* 상태를 바꾸거나 되돌리는 과정을 표현한 함수. */
    if (T == true)
    {
        MAP[x][y] = 0;
        MAP[nx][ny] = -1;
        Fish[Fish_Num].Live = false;
    }
    else
    {
        MAP[x][y] = -1;
        MAP[nx][ny] = Fish_Num;
        Fish[Fish_Num].Live = true;
    }
}
 
void DFS(int x, int y, int Dir, int Sum)
{
    /* 물고기의 움직임 + 상어의 움직임을 나타내는 DFS 함수. */
 
    Answer = Max(Answer, Sum);
    /* 현재 상태를 임시 변수를 선언해서 저장해 주기. */
    int C_MAP[4][4];
    FISH C_Fish[20];
    Copy_State(C_MAP, MAP, C_Fish, Fish);
    /*=========================================*/
    /* 물고기를 움직여주기 + 상어를 움직여주기 */
    Move_Fish();
 
    for (int i = 1; i <= 3; i++)
    {
        int nx = x + dx[Dir] * i;
        int ny = y + dy[Dir] * i;
        if (nx >= 0 && ny >= 0 && nx < 4 && ny < 4)
        {
            if (MAP[nx][ny] == 0) continue;
            
            int Fish_Num = MAP[nx][ny];
            int nDir = Fish[Fish_Num].Dir;
 
            Make_State(x, y, nx, ny, Fish_Num, true);
            DFS(nx, ny, nDir, Sum + Fish_Num);
            Make_State(x, y, nx, ny, Fish_Num, false);
        }
        else break;
    }
    /*==========================================*/
    Copy_State(MAP, C_MAP, Fish, C_Fish);
    /* 최종적으로 다시 원래의 상태로 되돌려 놓기. */
}
 
void Solution()
{
    /* 초기 세팅. 상어가 (0, 0)에 있는 물고기를 잡아먹는다. */
    int F_Num = MAP[0][0];
    int Dir = Fish[F_Num].Dir;
    Fish[F_Num].Live = false;
    MAP[0][0] = -1;
    /*================================================*/
    DFS(0, 0, Dir, F_Num);
    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;
}