[BOJ] C++ 1600 말이 되고픈 원숭이 - 제한 조건이 있는 BFS

1600번: 말이 되고픈 원숭이

예제

1
4 4
0 0 0 0
1 0 0 0
0 0 1 0
0 1 0 0

ans : 4

2
5 2
0 0 1 1 0
0 0 1 1 0

ans : -1

---

이 문제를 풀기 전에 아래의 벽 부수고 이동하기 문제를 꼭 꼭 먼저 푸는 것을 추천한다. 내가 떠올린 풀이가 아래 문제와 99% 비슷하기 때문이다.

[BOJ] C++ 2206 벽 부수고 이동하기 - BFS 활용

문제는 BFS를 돌리되, 나이트 움직임을 최대 K번 사용해서 돌려야 한다. 벽 부수고 이동하기 문제는 벽을 최대 한 번 부수고 이 문제는 최대 K번 나이트 움직임을 하기에 거의 유사하다고 생각했다. 그래서 바로 떠올린 게 dist를 3차원 배열로 정의하는 것이다.

 

dist [i][j][k] : (i, j)까지 나이트를 k번 쓰고 도달한 최단 거리

 

이렇게 dist를 정의하고 그냥 구현하면 된다. 다양한 문제를 풀어서 이득을 본 케이스이다.

/** BFS 1600 말이 되고픈 원숭이 **/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

int board[202][202];
int visited[202][202][32];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dkx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dky[8] = {1, -1, 2, -2, 2, -2, 1, -1};
int k, n, m; // n행 m열

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<pair<int, int>, int>> Q;
    cin >> k >> m >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];
    visited[0][0][0] = 1;
    Q.push(make_pair(make_pair(0, 0), 0));

    while (!Q.empty())
    {
        pair<int, int> cur = Q.front().first;
        int knight = Q.front().second;

        Q.pop();

        if (knight < k)
        {
            // 나이트 이동 가능
            for (int i = 0; i < 8; i++)
            {
                int nkx = cur.first + dkx[i];
                int nky = cur.second + dky[i];

                if (nkx < 0 || nky < 0 || nkx >= n || nky >= m)
                    continue;
                if (visited[nkx][nky][knight + 1] || board[nkx][nky])
                    continue;
                visited[nkx][nky][knight + 1] = visited[cur.first][cur.second][knight] + 1;
                Q.push(make_pair(make_pair(nkx, nky), knight + 1));
            }
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            //(nx, ny)는 cur의 상하좌우 칸이다.
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if (visited[nx][ny][knight] || board[nx][ny])
                continue;
            visited[nx][ny][knight] = visited[cur.first][cur.second][knight] + 1;
            Q.push(make_pair(make_pair(nx, ny), knight));
        }
    }
    int ans = 2100000000;
    for (int i = 0; i <= k; i++)
        if (visited[n - 1][m - 1][i])
            ans = min(ans, visited[n - 1][m - 1][i]);
    if (ans != 2100000000)
        cout << ans - 1;
    else
        cout << -1;
}