[C++] 백준 23290번: 마법사 상어와 복제

🔗 문제

23290번: 마법사 상어와 복제

23290번: 마법사 상어와 복제

 

✏️ 풀이

일단 이 문제는 내가 무려 밍기적 거리는 시간 포함해서 2주 동안 못 풀고 있던 것입니다.

이유는 예제 4, 5, 8에서 오답이 나와서, 다음은 예제 5번이 안 나와서.

 

총 2번의 대수정을 거쳐서 메모리 2028KB, 0ms로 문제로 맞았습니다!! 를 보게 됐다.

풀이 안 쓰려고 했는데 나한테도 도움될 것 같아서 오랜만에 자세히 써보고자 한다..

 

 

문제를 읽으면 알겠지만, 간단하게 과정 1~5로 나누면 아래와 같다.

while(S—)
1. 물고기 복제
2. 물고기 이동
3. 상어 이동
4. 2번전 물고기 냄새 제거
5. 과정 1번에서 복제된 물고기 생성

 

---

---

소스 짜면서 조건 맞추기 (과정2 & 과정3)

일단 물고기의 정보를 어떻게 저장할지 고민하는데 시간을 많이 썼다.

사실 이것만 해결하면 문제 50%는 다 푼 거나 마찬가지같다.

 

일단 문제를 보면 물고기가 복제되면서 물고기 수가 최악의 경우 2배씩 늘어날 수 있는데, 각 물고기가 이동할 때 필요에 따라 회전도 해야한다. 안 그래도 물고기가 많은데 한 마리씩 돌려가며 연산하는 방식으로 짜면 시간초과행이다. (경험담. 나름 시간줄이겠다고 리스트로도 짜봤는데 절대 통과 안 됨)

 

해결 방법은 같은 위치에서 방향이 같은 물고기는 한번에 옮겨주는 것이다!

int map[x][y][d] // 위치 (x, y)에 d 방향을 가진 물고기의 개수 저장

맵의 크기가 최대로 4X4며, 물고기의 이동방향은 8개라는 조건으로 O(4X4X8)로 해결 가능!

 

과정2. 물고기 이동

 

(1) 물고기가 한 칸씩 이동하며 이동 가능한 방향은 8가지며 이동 조건이 있다.
(2) 조건에 맞지 않으면, 현재 물고기의 방향에서 반시계방향으로 회전한다.
총 8방향이 있으니 (3) 모든 방향에서 이동이 불가능하다면 이동을 하지 않는다.

 

(1) 물고기는 한 칸씩 이동한다.

map에 저장된 물고기를 이동시킨 후 같은 map에 다가 물고기를 저장하면 이동했던 물고기가 또 이동할 수도 있다. 이를 위해 새로운 변수 moved 를 이용해준다.

 

이러면 과정1에서 물고기 굳이 복사 안 해도 된다.

map은 복사시점에 있던 물고기 상태 그대로니까 과정5에서 그냥 이동한 물고기만 다시 집어넣어주면 됩니다.

 

 

(2) 조건에 맞지 않으면, 현재 물고기의 방향에서 반시계방향으로 회전한다.

“현재 물고기의 방향”으로 먼저 시도 하고 이동조건이 맞지 않으면! 현재 방향에서 반시계 방향으로 회전하는 것이랍니다.

 

 

(3) 모든 방향을 다 돌았음에도 갈 수 있는 곳이 없으면 제자리에 있어야 한다.

이 부분을 위해서 standstill을 이용해 해결했다. (소스 참고)

나는 다 맞췄는데 이 부분을 놓쳐서 한참을 헤맸다.

 

bool standstill = true;
for (int d = 0; d < 8; ++d)
{
    int dir = (k - d + 8) % 8; // 원위치에서 반시계 방향으로 d번 이동
    int x = i + dx[dir];
    int y = j + dy[dir];

    //  범위 초과 || 냄새 있음 || 상어 있음
    if (!isValid(x, y) || fishy[x][y] != 0
        || (shark.first == x && shark.second == y))
        continue;

    moved[x][y][dir] += map[i][j][k];
    standstill = false;

    break;
}

if (standstill)
{
    // 물고기가 제자리
    moved[i][j][k]+= map[i][j][k];
}

 

과정3. 상어의 이동

 

(1) 상어가 연속 3칸 이동하며 이동 가능한 방향은 4가지며, 우선순위가 존재한다.
(2) 상어는 이동하며 물고기를 잡아먹으며 가장 많은 물고기를 잡아먹을 수 있는 경로로 이동한다.
(3) 물고기가 잡아먹히면 그 자리에 냄새를 남긴다.

 

이 부분은 다른 사람이 더 깔끔하게 짰을 것 같긴하지만 ~ 이것도 짜는데 굉장히 노력했기 때문에 기록해보겠습니다.

 

어느 경로로 가야지 물고기를 많이 잡을 수 있는지 모르기 때문에 3번 이동해서 갈 수 있는 모든 경로를 싹싹 뒤져야 한다. 이를 위해 DFS로 짰고 문제를 다시 보면 재방문하면 안된다는 이야기가 없다. 이때, 재방문했을 때 잡아먹은 물고기 수를 또 카운트하지 않게 해야 한다.

 

우선 순위를 맞추는 방법은 우선순위대로 방향 sdx, sdy를 만든 다음, 우선순위부터 이동한 다음에 죽은 물고기 수가 많을 때 갱신해주면 저절로 됩니다. (소스 참고)

 

이렇게 찾은 최종 경로(final_dir)는 이동할 때마다 물고기를 잡아먹는데 이동하지 않았을 때 초기 위치에선 물고기를 잡아먹으면 안된다.

백준 질문 게시판에 보면 이 부분에 대한 솔루션이 많던데 제 블로그 보신 분은 이걸로 실수하지 않길 바라여~

 

int tmp_dir[3], final_dir[3];
int findTrace(const Array3& map)
{
    int result = 0;

    std::pair<int, int> pos = { shark.first, shark.second };
    bool visited[4][4];
    memset(visited, false, sizeof(visited));

    for (int i = 0; i < 3; i++)
    {
        int dir = tmp_dir[i];
        int x = pos.first + sdx[dir];
        int y = pos.second + sdy[dir];

        // 재방문 하지 않은 곳을 물고기 개수 더해주기
        if (!visited[x][y])
        {
            visited[x][y] = true;
            for (int d = 0; d < 8; ++d)
            {
                result += map[x][y][d];
            }
        }
        pos = { x, y };
    }

    return result;
}

int kill_max = -1;
void DFS(int i, int j, int depth, const Array3& map)
{
    if (depth == 3)
    {
        int sum = findTrace(map);
        if (kill_max < sum)
        {
            for (int k = 0; k < 3; ++k)
                final_dir[k] = tmp_dir[k];

            kill_max = sum;
        }
        return;
    }

    for (int d = 0; d < 4; ++d)
    {
        int x = i + sdx[d];
        int y = j + sdy[d];

        if (!isValid(x, y))
            continue;

        tmp_dir[depth] = d;
        DFS(x, y, depth + 1, map);
    }
}

void MoveShark(Array3& moved, const int time)
{
    kill_max = -1; // 0으로 해놓으면 안 됨
    DFS(shark.first, shark.second, 0, moved);

    for (const auto& d : final_dir)
    {
        // 이동한 후 물고기를 잡아먹어야함
        shark.first += sdx[d];
        shark.second += sdy[d];

        for (int k = 0; k < 8; ++k)
        {
            if (moved[shark.first][shark.second][k] != 0)
            {
                //물고기가 죽었을 때만 물고기 냄새를 남겨야 함
                fishy[shark.first][shark.second] = time;
                moved[shark.first][shark.second][k] = 0;
            }
        }
    }
}

 

💾  소스

#include <iostream>
#include <queue>
#include <memory.h>

typedef std::vector<std::vector<int>> Array2;
typedef std::vector<Array2> Array3;

// ←, ↖, ↑, ↗, →, ↘, ↓, ↙
const int dx[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
const int dy[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };

// 상 좌 하 우
const int sdx[4] = { -1, 0, 1, 0 };
const int sdy[4] = { 0, -1, 0, 1 };

bool isValid(const int x, const int y)
{
    if (x < 0 || y < 0 || x >= 4 || y >= 4)
        return false;
    return true;
}

int T;
std::pair<int, int> shark;
Array2 fishy;

void debug(const Array3& arr)
{
    std::cout << "\\n================\\n";
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            int tmp = 0;
            for (int k = 0; k < 8; ++k)
            {
                tmp += arr[i][j][k];
            }
            std::cout << tmp << ' ';
        }
        std::cout << '\\n';
    }
    std::cout << "===================\\n";
}

void MoveFish(const Array3& map, Array3& moved)
{
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            for (int k = 0; k < 8; ++k)
            {
                if (map[i][j][k] == 0)
                    continue;

                bool standstill = true;
                for (int d = 0; d < 8; ++d)
                {
                    int dir = (k - d + 8) % 8; // 원위치에서 반시계 방향으로 d번 이동
                    int x = i + dx[dir];
                    int y = j + dy[dir];

                    //  범위 초과 || 냄새 있음 || 상어 있음
                    if (!isValid(x, y) || fishy[x][y] != 0
                        || (shark.first == x && shark.second == y))
                        continue;

                    moved[x][y][dir] += map[i][j][k];
                    standstill = false;

                    break;
                }

                if (standstill)
                {
                    // 물고기가 제자리 일 수도 있잖아 
                    moved[i][j][k]+= map[i][j][k];
                }
            }
        }
    }
}

int tmp_dir[3], final_dir[3];
int findTrace(const Array3& map)
{
    int result = 0;

    std::pair<int, int> pos = { shark.first, shark.second };
    bool visited[4][4];
    memset(visited, false, sizeof(visited));

    for (int i = 0; i < 3; i++)
    {
        int dir = tmp_dir[i];
        int x = pos.first + sdx[dir];
        int y = pos.second + sdy[dir];

        // 재방문 하지 않은 곳을 물고기 개수 더해주기
        if (!visited[x][y])
        {
            visited[x][y] = true;
            for (int d = 0; d < 8; ++d)
            {
                result += map[x][y][d];
            }
        }
        pos = { x, y };
    }

    return result;
}

int kill_max = -1;
void DFS(int i, int j, int depth, const Array3& map)
{
    if (depth == 3)
    {
        int sum = findTrace(map);
        if (kill_max < sum)
        {
            for (int k = 0; k < 3; ++k)
                final_dir[k] = tmp_dir[k];

            kill_max = sum;
        }
        return;
    }

    for (int d = 0; d < 4; ++d)
    {
        int x = i + sdx[d];
        int y = j + sdy[d];

        if (!isValid(x, y))
            continue;

        tmp_dir[depth] = d;
        DFS(x, y, depth + 1, map);
    }
}

void MoveShark(Array3& moved, const int time)
{
    kill_max = -1;
    DFS(shark.first, shark.second, 0, moved);

    for (const auto& d : final_dir)
    {
        shark.first += sdx[d];
        shark.second += sdy[d];

        for (int k = 0; k < 8; ++k)
        {
            if (moved[shark.first][shark.second][k] != 0)
            {
                fishy[shark.first][shark.second] = time;
                moved[shark.first][shark.second][k] = 0;
            }
        }
    }
}

//

void DisappearlSmell(const int time)
{
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            if (fishy[i][j] == time - 2)
                fishy[i][j] = 0;
        }
    }
}

void ShowEnsorcelledFish(const Array3& moved, Array3& map)
{
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            for (int k = 0; k < 8; ++k)
            {
                map[i][j][k] += moved[i][j][k];
            }
        }
    }
}

void input(Array3& inp)
{
    int M;
    int x, y, d;

    fishy.resize(4, std::vector<int>(4, 0));

    std::cin >> M >> T;
    while (M--)
    {
        std::cin >> x >> y >> d;
        ++inp[x - 1][y - 1][d - 1];
    }
    std::cin >> x >> y;
    shark = std::make_pair(x - 1, y - 1);
}

int solve()
{
    Array3 map(4, Array2(4, std::vector<int>(8, 0)));

    input(map);

    for (int time = 1; time <= T; ++time)
    {
        Array3 moved(4, Array2(4, std::vector<int>(8, 0)));

        MoveFish(map, moved);
        MoveShark(moved, time);
        DisappearlSmell(time);
        ShowEnsorcelledFish(moved, map);
    }

    int answer = 0;
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            for (int k = 0; k < 8; ++k)
                answer += map[i][j][k];
        }
    }

    return answer;

}

int main()
{
    std::cout << solve();

    return 0;
}