[BOJ] 23290 - 마법사 상어와 복제

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

23290번: 마법사 상어와 복제

난이도

구현 + dfs / 난이도 ⭐️⭐️⭐️ (오랜만에 풀어서 그런지 실수가 많았다) / 2일 ㅎㅎ...

 

분명 잘 짰는데 왜틀려? 라는 생각이 들면,
그냥 내가 틀린거다.
문제 조건을 빼먹고 구현하지 않았거나, 포문에서 i를 j로 썼다던지 실수가 있는것이 100%이다.

최초 구현 시, 예제 6번 부터 틀렸다는 결과가 나왔다. 예제 6번은 모든 과정을 10번 반복해야하는 예제로 종이에 그림을 그려 시뮬레이션 해볼 수 없었다.
4번 반복처럼 시뮬레이션 할 수 있는 수준이었다면 '문제 조건'과 내가 짠 '코드'를 먼저 살펴보는 대신에 종이에 그림을 그려봤을 것 같다. 본 문제에서는 우연히 문제조건과 코드를 먼저 점검하게 되었지만, 아무리 시뮬레이션 가능한 테스트케이스라도 문제조건과 코드를 점검하는 것이 우선인 것 같다.

 

---

틀린 포인트1, 2. 상어 이동 부분에서 두 가지 실수가 있었다.

물고기를 가장 많이 잡아먹고, 우선순위가 높은 경로를 max_fish_die_path에 저장했다. 하지만 경로를 '이동 후 좌표인지' '이동 방향을 나타낸 좌표인지' 명확히 설계를 하지 않았다. 

(1,1)좌표에서 오른쪽으로 한칸 간다고 가정한다면

'이동 후 좌표'는 (1,2)가 될 것이고, '이동 방향을 나타내는 좌표는' (0, 1)이라고 표현될 것이다.

 

max_fish_die_path에는 상어의 '이동 후 좌표'를 저장해두었지만, 물고기를 제거하기 위해 max_fish_die_path를 돌면서 상어의 좌표를 계산하는 과정에서는 다음과 같이 코드를 잘못 작성했다.

newx = 현재 상어의x좌표 + max_fish_die_path[i].first;
newy = 현재 상어의y좌표 + max_fish_die_path[i].second;

다음과 같이 수정했다.

newx = max_fish_die_path[i].first;
newy = max_fish_die_path[i].second;

 

 

또 다른 치명적인 실수는 DFS에서 지나온 길을 갈수있는지 없는지 고려하지 않았다는 점이다.

본 문제에서는 돌아갈 수 있으나 돌아간다면 물고기는 이미 먹힌상태이기 때문에 '먹힌 물고기 개수'에 포함하지 않는다는 점이다.

DFS로 재귀에 들어가기 전 moved_fish_cnt[][] = 0코드를 통해 해결할 수 있었다.

cur_fish_die_path.push_back({newx, newy});
box_fish_cnt = moved_fish_cnt[newx][newy];
moved_fish_cnt[newx][newy] = 0;
shark_move(newx, newy, fish_die + box_fish_cnt, move_cnt + 1);
moved_fish_cnt[newx][newy] = box_fish_cnt;
cur_fish_die_path.pop_back();

 

두 가지 실수를 수정 후 예제5번까지는 통과 되었다.

 

 

틀린 포인트3,4. 물고기 이동 부분에서도 두 가지 실수가 있었다.

만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 라는 문제 지문을 주의깊게 보지 않았다.

내가 작성한 코드에서는 vector<fish_s> fish_arr 배열을 포문을 돌며, vector<fish_s> moved_fish[5][5]에 물고기의 움직인 위치를 저장하고 있었다. 하지만 어느 방향으로도 갈 수 없는 경우 현재 위치를 그대로 moved_fish에 넣어줘야 했으나, "아예 넣어주지를 않았다."

 

다음과 같이 isFishMove boolean을 활용한 조건문을 추가한 뒤 문제를 해결할 수 있었다. 이와중에 newd = fish_arr[i].d; 부분을 넣어주지 않아서 마지막 테스트케이스인 예제 입력8번이 통과되지 않았다. 

if (!isFishMove)
{
    newx = fish_arr[i].x;
    newy = fish_arr[i].y;
    newd = fish_arr[i].d; // 틀린 포인트 3
    moved_fish[newx][newy].push_back({newx, newy, newd});
    moved_fish_cnt[newx][newy] += 1;
 }

 

 

---

헷갈렸던 포인트1. 

상어 이동 시, 이동 전 상어가 있는 칸에 물고기가 존재하는 경우 물고기를 잡아먹어야하는지 아닌지 헷갈렸다. 

지문 중 아래 문장 때문에 최초에 물고기와 상어 위치가 주어질 때 같은 공간이 있을 가능성이 있다고 생각했다. 

상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.

아래와 같은 코드를 작성했었으나, 필요하지 않았고 문제는 틀린포인트4에 있었다.

문제 언급된 부분이 아니기 때문에 구현을 하지 않는 것이 맞다.

	//최초 세팅시 물고기와 상어가 같은 칸이 있을 수 있다.
    // if (moved_fish[shark.x][shark.y].size() != 0)
    // {
    //     moved_fish[shark.x][shark.y].clear();
    //     smell[shark.x][shark.y] = cnt;
    // }

 

---

정답 코드

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

struct fish_s
{
    int x;
    int y;
    int d;
};

struct shark_s
{
    int x;
    int y;
};

int M, S;
vector<fish_s> fish_arr;
shark_s shark;

int smell[5][5];
vector<fish_s> moved_fish[5][5];
int moved_fish_cnt[5][5];

int fish_x[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int fish_y[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

int shark_x[4] = {-1, 0, 1, 0};
int shark_y[4] = {0, -1, 0, 1};

int max_fish_die;
vector<pair<int, int> > max_fish_die_path;
vector<pair<int, int> > cur_fish_die_path;
void shark_move(int curx, int cury, int fish_die, int move_cnt)
{
    if (move_cnt == 3)
    {
        if (fish_die > max_fish_die)
        {
            max_fish_die = fish_die;
            max_fish_die_path.clear();
            for (int i = 0; i < cur_fish_die_path.size(); i++)
            {
                max_fish_die_path.push_back({cur_fish_die_path[i].first, cur_fish_die_path[i].second});
            }
        }
        return;
    }

    int newx, newy, box_fish_cnt;
    for (int i = 0; i < 4; i++)
    {
        newx = curx + shark_x[i];
        newy = cury + shark_y[i];

        if (newx < 1 || newx > 4 || newy < 1 || newy > 4)
            continue;

        cur_fish_die_path.push_back({newx, newy});
        box_fish_cnt = moved_fish_cnt[newx][newy];
        moved_fish_cnt[newx][newy] = 0;
        shark_move(newx, newy, fish_die + box_fish_cnt, move_cnt + 1);
        moved_fish_cnt[newx][newy] = box_fish_cnt;
        cur_fish_die_path.pop_back();
    }
}

void process(int cnt)
{
    for (int i = 1; i < 5; i++)
    {
        for (int j = 1; j < 5; j++)
        {
            moved_fish[i][j].clear();
            moved_fish_cnt[i][j] = 0;
        }
    }

    // 2. 물고기 이동
    int newx, newy, newd;
    bool isFishMove = false;
    for (int i = 0; i < fish_arr.size(); i++)
    {
        isFishMove = false;
        for (int j = 0; j < 8; j++)
        {
            newd = fish_arr[i].d - j;
            if (newd < 0)
                newd += 8;
            newx = fish_arr[i].x + fish_x[newd];
            newy = fish_arr[i].y + fish_y[newd];

            //범위 벗어나는지
            if (newx < 1 || newx > 4 || newy < 1 || newy > 4)
                continue;
            //상어자리인지
            if (newx == shark.x && newy == shark.y)
                continue;
            //냄새칸인지
            if (smell[newx][newy] != 0 && cnt - smell[newx][newy] <= 2)
                continue;

            moved_fish[newx][newy].push_back({newx, newy, newd});
            moved_fish_cnt[newx][newy] += 1;
            isFishMove = true;
            break;
        }
        if (!isFishMove)
        {
            newx = fish_arr[i].x;
            newy = fish_arr[i].y;
            newd = fish_arr[i].d; // check point 3
            moved_fish[newx][newy].push_back({newx, newy, newd});
            moved_fish_cnt[newx][newy] += 1;
        }
    }

    //  3. 상어 이동
    max_fish_die = -1;
    cur_fish_die_path.clear();
    max_fish_die_path.clear();

    shark_move(shark.x, shark.y, 0, 0);

    //최초 세팅시 물고기와 상어가 같은 칸이 있을 수 있다.
    // if (moved_fish[shark.x][shark.y].size() != 0)
    // {
    //     moved_fish[shark.x][shark.y].clear();
    //     smell[shark.x][shark.y] = cnt;
    // }
    for (int i = 0; i < max_fish_die_path.size(); i++)
    {
        newx = max_fish_die_path[i].first;
        newy = max_fish_die_path[i].second;

        if (moved_fish[newx][newy].size() != 0)
        {
            moved_fish[newx][newy].clear();
            smell[newx][newy] = cnt;
        }
    }
    shark.x = newx;
    shark.y = newy;

    // 5.
    for (int i = 1; i < 5; i++)
    {
        for (int j = 1; j < 5; j++)
        {
            if (moved_fish[i][j].size() == 0)
                continue;

            for (int k = 0; k < moved_fish[i][j].size(); k++)
            {
                fish_arr.push_back({i, j, moved_fish[i][j][k].d});
            }
        }
    }
}

int main()
{

    scanf("%d %d", &M, &S);

    int a, b, c;
    for (int i = 1; i <= M; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        fish_s fish;
        fish.x = a;
        fish.y = b;
        fish.d = c - 1;
        fish_arr.push_back(fish);
    }

    scanf("%d %d", &shark.x, &shark.y);

    for (int i = 1; i <= S; i++)
    {
        process(i);
    }

    printf("%d", fish_arr.size());
}