[백준/C++] 말이 되고픈 원숭이

문제

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

---

문제 요약

N × M 크기의 격자판이 존재할 때, (0, 0)에서 (N - 1, M - 1)까지 이동하고자 한다.

 

2가지 방법으로 칸을 이동할 수 있다.

 

1. 상하좌우로 인접한 칸을 1번의 동작으로 움직일 수 있다.

2. 체스에서의 나이트처럼 칸을 1번의 동작으로 움직일 수 있다.

 

이 때, 2번째 방법은 K번만 움직일 수 있고, 장애물이 있는 칸(1)으로는 이동할 수 없다.

 

시작지점에서 도착지점까지 갈 수 있는 최소한의 동작 횟수를 출력한다.

---

코드

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

using namespace std;

int n, m, k;

int board[220][220];

// (0, 0)에서 (i, j)까지 말처럼 k번 이동한 최소 동작 횟수
int dp[220][220][33];

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int dx_k[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dy_k[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };

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

    cin >> k >> m >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            
            // dp 배열 초기화
            for (int kk = 0; kk <= k; kk++) {
                dp[i][j][kk] = 1e9;
            }
        }
    }

    queue<tuple<int, int, int>> q;
    dp[0][0][0] = 0;
    q.push({ 0, 0, 0 });

    while (!q.empty()) {
        int x, y, cnt_k;
        tie(x, y, cnt_k) = q.front();
        q.pop();

        // 그냥 이동
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            // 범위에서 벗어나는 경우
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            // 이동한 위치에 장애물이 있는 경우
            if (board[nx][ny] == 1) continue;

            // 이미 더 적은 동작 횟수로 도달했던 경우
            if (dp[nx][ny][cnt_k] <= dp[x][y][cnt_k] + 1) continue;

            dp[nx][ny][cnt_k] = dp[x][y][cnt_k] + 1;

            q.push({ nx, ny, cnt_k });
        }

        // 말처럼 이동
        for (int d = 0; d < 8; d++) {
            int nx = x + dx_k[d];
            int ny = y + dy_k[d];

            // 범위에서 벗어나는 경우
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            // 이동한 위치에 장애물이 있는 경우
            if (board[nx][ny] == 1) continue;

            // 이미 더 적은 동작 횟수로 도달했던 경우
            if (dp[nx][ny][cnt_k + 1] <= dp[x][y][cnt_k] + 1) continue;

            dp[nx][ny][cnt_k + 1] = dp[x][y][cnt_k] + 1;

            q.push({ nx, ny, cnt_k + 1});
        }
    }

    int res = 1e9;

    // 목표 지점까지 최소 동작 횟수 탐색
    for (int kk = 0; kk <= k; kk++) {
        res = min(res, dp[n - 1][m - 1][kk]);
    }

    if (res == 1e9) {
        cout << -1;
    }
    else {
        cout << res;
    }

    return 0;
}

---

코드 설명

3차원 DP와 BFS 탐색을 통해 문제를 해결한다.

 

1. 격자판 정보를 입력 받고, dp 배열을 초기화한다. (최소를 찾기 위해 무한대로 초기화)

- dp[i][j][k]는 (0, 0)에서 (i, j)까지 2번째 이동 방법을 k번 사용하여 이동한 최소 동작 횟수이다.

 

2. (0, 0)부터 Queue를 이용하여 BFS 탐색을 진행한다.

- 1번째 이동 방법으로 이동하는 경우와 2번째 이동 방법으로 이동하는 경우를 모두 탐색한다.

 

3. (0, 0)에서 (i, j)까지 2번째 이동 방법을 k번 이하로 사용한 동작 횟수 중 최소를 찾고 출력한다.

- 일단 2번째 이동 방법 사용 횟수를 고려하지 않고, 이 과정에서 k번 초과로 사용한 방법 탐색에서 제외한다.