[BOJ] 19236 - 청소년 상어

https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

 

난이도

구현 + dfs / 난이도 ⭐️⭐️ / 2시간

 

주의할 점

문제 자체는 명확하고 크게 어렵지 않았으나, dfs에서  return시 배열자체를 이전 상태로 되돌리는건 처음이라서 

검색해보고  알았다. 변수정도는 이전 상태로 되돌리는 경우가 많았지만 배열자체를 이전 상태로 되돌려야해서 어색했다.

 

최초로 제출 시, 로컬에서는 1개  테스트케이스가 segmentation fault 뜨고, 백준에서는 메모리  초과가  떴다.

인덱스를 잘못 접근했거나, dfs하는 중에 메모리가 초과 되었을 거라고 예상했다. 결국 check point 1에 조건을 빼먹어서 인덱스를 잘못  접근 했던 것 같다.

 

제출 후 틀렸을 때, 디버깅하지않고 코드를 차분하게 읽어서 빠르게 수정할 수 있었다.

#include <stdio.h>
#include <vector>
#include <utility>
using namespace std;

int arr[4][4][2] = {0};
vector<vector<int> > fishs(17, vector<int>(2, 0));
int dirx[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1}; // 위부터 왼쪽으로 45도씩 회전
int diry[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int result;

int gen_dir(int n)
{
    if (n > 8)
    {
        return n - 8;
    }
    else
    {
        return n;
    }
}

void fish_exchange(int fish1, int newdir, int fish2)
{
    int x1 = fishs[fish1][0];
    int y1 = fishs[fish1][1];
    int dir1 = newdir;

    int x2 = fishs[fish2][0];
    int y2 = fishs[fish2][1];
    int dir2 = arr[x2][y2][1];

    // 2 => 1
    fishs[fish2][0] = x1;
    fishs[fish2][1] = y1;
    arr[x2][y2][0] = fish1;
    arr[x2][y2][1] = dir1;

    // 1 => 2
    fishs[fish1][0] = x2;
    fishs[fish1][1] = y2;
    arr[x1][y1][0] = fish2;
    arr[x1][y1][1] = dir2;
}

void copy_state(int c_arr[][4][2], int c_fishs[16][2])
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            c_arr[i][j][0] = arr[i][j][0];
            c_arr[i][j][1] = arr[i][j][1];
        }
    }

    for (int i = 1; i < fishs.size(); i++)
    {
        c_fishs[i - 1][0] = fishs[i][0];
        c_fishs[i - 1][1] = fishs[i][1];
    }
}

void reset_state(int c_arr[][4][2], int c_fishs[16][2])
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            arr[i][j][0] = c_arr[i][j][0];
            arr[i][j][1] = c_arr[i][j][1];
        }
    }

    for (int i = 0; i < 16; i++)
    {
        fishs[i + 1][0] = c_fishs[i][0];
        fishs[i + 1][1] = c_fishs[i][1];
    }
}

void dfs(int fish_sum, int sharkx, int sharky, int sharkdir)
{
    // printf("hi: %d\n", fish_sum);
    if (result < fish_sum)
    {
        result = fish_sum;
    }

    // copy
    int c_arr[4][4][2] = {0};
    int c_fishs[16][2] = {0};
    copy_state(c_arr, c_fishs); // check_point 2) dfs에서 배열 되돌리기

    // 1번 물고기 부터 이동
    int x, y, dir, newx, newy, newdir;
    for (int i = 1; i < fishs.size(); i++)
    {
        // printf("fish: %d\n", i);
        x = fishs[i][0];
        y = fishs[i][1];
        if (x == -1 && y == -1)
            continue;

        dir = arr[x][y][1];

        for (int j = 0; j < 8; j++)
        {
            newdir = gen_dir(dir + j);
            newx = x + dirx[newdir];
            newy = y + diry[newdir];

            if (newx < 0 || newy < 0 || newx >= 4 || newy >= 4)
                continue;

            // 상어
            if (arr[newx][newy][0] == -1)
            {
                continue;
                //빈칸
            }
            else if (arr[newx][newy][0] == 0)
            {
                arr[newx][newy][0] = i;
                arr[newx][newy][1] = newdir;
                arr[x][y][0] = 0;
                arr[x][y][1] = 0;

                // check point 1) 최초 코드에서 이 조건을 빼먹어서, 메모리 초과 / 로컬에서는 segmentation fault
                fishs[i][0] = newx;
                fishs[i][1] = newy;
                break;
            }
            else
            {
                // 교환
                fish_exchange(i, newdir, arr[newx][newy][0]);
                break;
            }
        }
    }

    // 상어가 움직일 수 있는 최대 4가지 케이스

    newx = sharkx;
    newy = sharky;
    for (int i = 0; i < 4; i++)
    {
        newx += dirx[sharkdir];
        newy += diry[sharkdir];

        if (newx < 0 || newy < 0 || newx >= 4 || newy >= 4)
        {
            break;
        }

        if (arr[newx][newy][0] == 0)
        {
            continue;
        }
        else
        {
            //물고기 먹기
            int removed_fish_num = arr[newx][newy][0];
            int removed_fish_dir = arr[newx][newy][1];
            int removed_fish_x = fishs[arr[newx][newy][0]][0];
            int removed_fish_y = fishs[arr[newx][newy][0]][1];

            fishs[arr[newx][newy][0]][0] = -1;
            fishs[arr[newx][newy][0]][1] = -1;

            //상어 이동
            arr[sharkx][sharky][0] = 0;
            arr[sharkx][sharky][1] = 0;
            arr[newx][newy][0] = -1;

            dfs(fish_sum + removed_fish_num, newx, newy, removed_fish_dir);

            arr[newx][newy][0] = removed_fish_num;
            arr[sharkx][sharky][1] = sharkdir;
            arr[sharkx][sharky][0] = -1;

            fishs[arr[newx][newy][0]][0] = removed_fish_x;
            fishs[arr[newx][newy][0]][1] = removed_fish_y;
        }
    }

    // copy
    reset_state(c_arr, c_fishs); // check_point2) dfs에서 배열 되돌리기

    return;
}

void solve()
{
    int fish_num = arr[0][0][0];

    arr[0][0][0] = -1;
    fishs[fish_num][0] = -1;
    fishs[fish_num][1] = -1;

    dfs(fish_num, 0, 0, arr[0][0][1]);
}

void question_input()
{
    int a, b;
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            scanf("%d %d", &a, &b);
            arr[i][j][0] = a; // 물고기 번호
            arr[i][j][1] = b; // 물고기 방향
            fishs[a][0] = i;
            fishs[a][1] = j;
        }
    }

    // for (int i = 0; i < 4; i++)
    // {
    //     for (int j = 0; j < 4; j++)
    //     {
    //         printf("%d %d ", arr[i][j][0], arr[i][j][1]);
    //     }
    //     printf("\n");
    // }
}

int main()
{
    question_input();
    result = 0;
    solve();
    printf("%d", result);
}