(2024-11-07) 2 문제 : 백준 - 1600 (말이 되고픈 원숭이)

 

BFS를 통해 경우의 수를 모두 탐색하면 된다. 다만, 각 좌표의 방문체크를 1번만 해도 지나갈 수 없게 된다면 정답을 구할 수가 없게 된다. 그러므로 방문체크 배열을 [K + 1][Height ][Width] 의 크기를 가진 3차원 배열로 선언하여 사용해야 한다.

 

BFS를 할 때마다, 현재 남은 말 이동 횟수를 카운팅하며 해당 카운팅과 동일한 카운팅을 가진 상태로 다음 좌표에 진입한 적이 있는지를 체크하는 것이다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <climits>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int HorseCount = 0;
    std::cin >> HorseCount;

    int Width = 0, Height = 0;
    std::cin >> Width >> Height;

    std::vector<std::vector<int>> Board(Height, std::vector<int>(Width));
    for (int i = 0; i < Height; i++)
    {
        for (int j = 0; j < Width; j++)
        {
            std::cin >> Board[i][j];
        }
    }

    std::vector<std::vector<std::vector<bool>>> IsVisit(31, std::vector<std::vector<bool>>(Height, std::vector<bool>(Width)));
    IsVisit[0][0][0] = true;

    std::queue<std::tuple<int, int, int, int>> BFS;
    BFS.push({ 0, 0, 0, HorseCount });

    std::vector<int> DirX = { 0, 1, 0, -1 };
    std::vector<int> DirY = { 1, 0, -1, 0 };

    std::vector<int> HorseDirX = { -2, -2, -1, -1, 1, 1, 2, 2 };
    std::vector<int> HorseDirY = { -1, 1, -2, 2, -2, 2, -1, 1 };

    int Answer = INT_MAX;

    while (BFS.size() > 0)
    {
        auto [CurY, CurX, MoveCount, CurHorseCount] = BFS.front();
        BFS.pop();

        if (CurY == Height - 1 && CurX == Width - 1)
        {
            Answer = std::min(Answer, MoveCount);
            continue;
        }

        for (int i = 0; i < 4; i++)
        {
            int NextX = CurX + DirX[i];
            int NextY = CurY + DirY[i];

            if (NextX < 0 || NextY < 0 || NextX >= Width || NextY >= Height)
            {
                continue;
            }

            if (IsVisit[CurHorseCount][NextY][NextX] == true)
            {
                continue;
            }

            if (Board[NextY][NextX] == 1)
            {
                continue;
            }

            IsVisit[CurHorseCount][NextY][NextX] = true;
            BFS.push({ NextY, NextX, MoveCount + 1, CurHorseCount });
        }

        if (CurHorseCount == 0)
        {
            continue;
        }

        for (int i = 0; i < 8; i++)
        {
            int NextX = CurX + HorseDirX[i];
            int NextY = CurY + HorseDirY[i];

            if (NextX < 0 || NextY < 0 || NextX >= Width || NextY >= Height)
            {
                continue;
            }

            if (IsVisit[CurHorseCount - 1][NextY][NextX] == true)
            {
                continue;
            }

            if (Board[NextY][NextX] == 1)
            {
                continue;
            }

            IsVisit[CurHorseCount - 1][NextY][NextX] = true;
            BFS.push({ NextY, NextX, MoveCount + 1, CurHorseCount - 1 });
        }
    }

    if (Answer == INT_MAX)
    {
        Answer = -1;
    }

    std::cout << Answer;
    return 0;
}