[Problem Solving] BOJ 19236 : 청소년 상어

문제 링크 : https://www.acmicpc.net/problem/19236

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

struct Fish
{
    int y;
    int x;
    int direction;
    bool isLive;
};
int graph[4][4];
Fish fishes[17];
int dy[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int dx[] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int answer = 0;

void input();
void copy_state(int[][4], int[][4], Fish[], Fish[]);
bool isValid(int, int);
void swap_fish(int, int);
void move_fish();
void move_shark(int, int, int, int);
void make_state(int, int, int, int, int, bool);
void dfs(int, int, int, int);
void solve();
void output();

void input()
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int number, direction;
            cin >> number >> direction;
            graph[i][j] = number;
            fishes[number] = {
                i,
                j,
                direction,
                true};
        }
    }
}

void copy_state(int copied_graph[][4], int graph[][4], Fish copied_fishes[], Fish fishes[])
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            copied_graph[i][j] = graph[i][j];
        }
    }

    for (int i = 1; i <= 16; i++)
    {
        copied_fishes[i] = fishes[i];
    }
}

bool isValid(int y, int x)
{
    return (0 <= y && y < 4 && 0 <= x && x < 4);
}

void swap_fish(int a, int b)
{
    Fish temp = fishes[a];
    fishes[a].y = fishes[b].y;
    fishes[a].x = fishes[b].x;
    fishes[b].y = temp.y;
    fishes[b].x = temp.x;
}

void move_fish()
{
    for (int i = 1; i <= 16; i++)
    {
        if (fishes[i].isLive != true)
            continue;
        int y = fishes[i].y;
        int x = fishes[i].x;
        int dir = fishes[i].direction;

        int ny = y + dy[dir];
        int nx = x + dx[dir];
        bool flag = false;

        if (isValid(ny, nx))
        {
            if (graph[ny][nx] == 0)
            {
                flag = true;
                fishes[i].y = ny;
                fishes[i].x = nx;
                graph[ny][nx] = i;
                graph[y][x] = 0;
            }
            else if (graph[ny][nx] != -1)
            {
                flag = true;
                swap_fish(i, graph[ny][nx]);
                swap(graph[y][x], graph[ny][nx]);
            }
        }

        if (flag == false)
        {
            int next_dir = dir;
            if (++next_dir == 9)
                next_dir = 1;
            int ny = y + dy[next_dir];
            int nx = x + dx[next_dir];

            while (next_dir != dir)
            {
                if (isValid(ny, nx))
                {
                    if (graph[ny][nx] == 0)
                    {
                        fishes[i].y = ny;
                        fishes[i].x = nx;
                        graph[ny][nx] = i;
                        graph[y][x] = 0;
                        fishes[i].direction = next_dir;
                        break;
                    }
                    else if (graph[ny][nx] != -1)
                    {
                        swap_fish(i, graph[ny][nx]);
                        swap(graph[y][x], graph[ny][nx]);
                        fishes[i].direction = next_dir;
                        break;
                    }
                }
                if (++next_dir == 9)
                    next_dir = 1;
                ny = y + dy[next_dir];
                nx = x + dx[next_dir];
            }
        }
    }
}

void make_state(int y, int x, int ny, int nx, int fishNum, bool flag)
{
    if (flag == true)
    {
        graph[y][x] = 0;
        graph[ny][nx] = -1;
        fishes[fishNum].isLive = false;
    }
    else if (flag == false)
    {
        graph[y][x] = -1;
        graph[ny][nx] = fishNum;
        fishes[fishNum].isLive = true;
    }
}

void move_shark(int y, int x, int dir, int sum)
{
    for (int i = 1; i <= 3; i++)
    {
        int ny = y + i * dy[dir];
        int nx = x + i * dx[dir];
        if (isValid(ny, nx))
        {
            if (graph[ny][nx] == 0)
                continue;
            int cur_fishNum = graph[ny][nx];
            int cur_dir = fishes[cur_fishNum].direction;
            make_state(y, x, ny, nx, cur_fishNum, true);
            dfs(ny, nx, cur_dir, sum + cur_fishNum);
            make_state(y, x, ny, nx, cur_fishNum, false);
        }
        else
            break;
    }
}

void dfs(int y, int x, int dir, int sum)
{
    answer = max(answer, sum);
    int copied_graph[4][4];
    Fish copied_fishes[17];

    copy_state(copied_graph, graph, copied_fishes, fishes);
    move_fish();
    move_shark(y, x, dir, sum);
    copy_state(graph, copied_graph, fishes, copied_fishes);
}

void solve()
{
    int cur_fishNum = graph[0][0];
    int cur_dir = fishes[cur_fishNum].direction;
    fishes[cur_fishNum].isLive = false;
    graph[0][0] = -1;
    dfs(0, 0, cur_dir, cur_fishNum);
}

void output()
{
    cout << answer << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    input();
    solve();
    output();
    return 0;
}

graph의 각 원소는 0일 때 비어있는 곳, -1 일때 상어가 있는 곳, 1~16 일때는 물고가가 있는 곳임을 의미한다.

fishes는 1번부터 16번 물고기의 상태를 나타내는 Fish 구조체 타입의 배열이다.

 

1. 상어는 (0, 0) 위치에 있는 물고기부터 잡아먹고, 그 물고기와 같은 방향을 향한다. 그리고 잡아 먹힌 물고기의 isLive는 false가 되고, graph[0][0]는 -1이 된다.

 

2. (0, 0)을 기점으로 하여 가능한 모든 조합을 dfs하여 answer의 최댓값을 찾는다.

2-1. 물고기를 이동시키기 전에 fishes와 graph를 복제하여 놓는다.

2-2. 물고기를 이동시킨다. (물고기가 이동하는 방식은 빈 자리로 이동하는 방식, 다른 물고기와 자리를 바꾸는 방식으로 두가지이다.)

2-3. 상어를 이동시키는데, 모든 조합을 탐색해야 하기 때문에, 물고기를 잡아 먹고 dfs를 재귀 호출 한 후, 재귀 호출이 끝나면 다시 물고기를 잡아 먹기 전 상태로 돌아온다.

2-4. 복제해 놓은 fishes와 graph를 복구한다.

 

3. 완전 탐색 후 얻은 answer의 최댓값을 출력한다.