[ 백준 1600 ] 말이 되고픈 원숭이 (C++)

백준의 말이 되고픈 원숭이(1600) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 시작점에서 끝점까지 가야하는 원숭이가 있는데, 이 원숭이는 상하좌우로 인접한 곳으로만 갈 수 있다.

- 원숭이는 K번 동안 말처럼 움직일 수 있으며, 말의 움직임은 다음과 같다.

- 이 때, 원숭이가 움직인 최소횟수를 출력시키면 된다.

- 맵에는 장애물이 있어서 갈 수 없는 곳과 장애물이 없는 평지 2가지로 이루어져 있다.

[ 문제풀이 ]

1. 일반적인 BFS/DFS 풀이법으로 접근하면 굉장히 쉽게 풀 수 있는 문제이다. 다만 조심해야 할 부분은

   말 처럼 움직일 수 있을 때가 있기 때문에 이 부분을 조심해야 한다.

2. 1)에서 했던 말을 조금 더 구체적으로 해보자면, "이미 탐색했던 정점이더라도, 다른 경우일 수가 있다" 라고

   표현할 수 있다. 말이 조금 이상하긴 한데, 어떤 한 정점(a,b)가 있다고 생각해보자.

   원숭이가 말의 능력을 0번 사용하고 (a, b)에 도달한 경우와, 원숭이가 말의 능력을 1번 사용하여 (a, b)에 도달한 경우가

   있다고 생각해보자. 같은 (a, b)라는 정점이지만, 능력을 몇 번 사용해서 왔는지, 사용하지 않고 왔는지에 따라서

   그 정점까지의 최소횟수가 달라질 수 있기 때문에, 이미 탐색한 정점이라고 해서 그냥 지나치면 안된다.

   말의 능력따위는 없고, 원숭이의 움직임으로만 움직이는 문제였다면, (a, b)라는 정점을 탐색했다면 이미 탐색했으므로

   다시 탐색을 하지는 않을 것이다. 왜냐하면, 이미 탐색을 했다는 말은 이미 최소횟수로 해당 정점까지 왔다는 의미이기 때문이다

3. 따라서 위의 부분을 해결하기 위해서 3차원 Visit배열을 사용하였다.

   Visit[x][y][a] 를 사용하였는데 이 배열의 의미는 "(x,y)지점에 능력을 a번 사용해서 왔습니다" 이다.

4. 본인은 BFS로 문제를 해결하였는데, Queue에서 4개의 값을 관리해주었다.

   [ (x,y), (이동횟수, 능력사용횟수) ] 이렇게 4개의 값을 사용하였다.

   매번 Queue가 반복될 때마다, 현재 능력사용횟수와, 능력을 사용할 수 있는 최대 횟수 값을 비교해가면서 아직 사용할 수 있는

   기회가 남아있다면, 사용할 수 있도록 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 200
using namespace std;
 
int W, H, K;
int MAP[MAX][MAX];
bool Visit[MAX][MAX][31];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int hdx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int hdy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
 
void Input()
{
    cin >> K;
    cin >> W >> H;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(0, 0), make_pair(0, 0)));
    Visit[0][0][0] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second.first;
        int Ability = Q.front().second.second;
        Q.pop();
 
        if (x == H - 1 && y == W - 1)
        {
            cout << Cnt << endl;
            return;
        }
        if (Ability < K)
        {
            for (int i = 0; i < 8; i++)
            {
                int nx = x + hdx[i];
                int ny = y + hdy[i];
                if (nx >= 0 && ny >= 0 && nx < H && ny < W)
                {
                    if (MAP[nx][ny] == 0 && Visit[nx][ny][Ability + 1] == false)
                    {
                        Visit[nx][ny][Ability + 1] = true;
                        Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, Ability + 1)));
                    }
                }
            }
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < H && ny < W)
            {
                if (MAP[nx][ny] == 0 && Visit[nx][ny][Ability] == false)
                {
                    Visit[nx][ny][Ability] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, Ability)));
                }
            }
        }
    }
    cout << -1 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}