[백준] 1600번 말이 되고픈 원숭이 C++ 코드

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int mdx[] = {1, -1, 0, 0};
const int mdy[] = {0, 0, 1, -1};
const int hdx[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int hdy[] = {1, 2, 2, 1, -1, -2, -2, -1};
const int INF = 987654321;
int k, w, h, a[203][203], visited[203][203][32];

struct Node {
    int x, y, dist, horseMoves;
};

int bfs() {
    queue<Node> q;
    q.push({0, 0, 0, k});
    visited[0][0][k] = 1;

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        int x = cur.x;
        int y = cur.y;
        int dist = cur.dist;
        int horseMoves = cur.horseMoves;

        // 목표 지점에 도착한 경우
        if (x == h - 1 && y == w - 1) {
            return dist;
        }

        // 말처럼 움직일 수 있는 경우
        if (horseMoves > 0) {
            for (int i = 0; i < 8; i++) {
                int nx = x + hdx[i];
                int ny = y + hdy[i];
                if (nx >= 0 && nx < h && ny >= 0 && ny < w && a[nx][ny] == 0 && !visited[nx][ny][horseMoves - 1]) {
                    visited[nx][ny][horseMoves - 1] = 1;
                    q.push({nx, ny, dist + 1, horseMoves - 1});
                }
            }
        }

        // 일반적인 4방향 움직임
        for (int i = 0; i < 4; i++) {
            int nx = x + mdx[i];
            int ny = y + mdy[i];
            if (nx >= 0 && nx < h && ny >= 0 && ny < w && a[nx][ny] == 0 && !visited[nx][ny][horseMoves]) {
                visited[nx][ny][horseMoves] = 1;
                q.push({nx, ny, dist + 1, horseMoves});
            }
        }
    }

    // 도착할 수 없는 경우
    return -1;
}

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

    cin >> k; // 말처럼 움직일 수 있는 횟수
    cin >> w >> h;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }

    memset(visited, 0, sizeof(visited));

    int result = bfs();
    cout << result << '\n';

    return 0;
}

풀이

말처럼 움직일 수 있는 케이스와 원숭이처럼 움직일 수 있는 케이스를 구분해서 bfs를 구성해주면 된다. 최소동작횟수를 구하는 것이기 때문에 bfs를 쓰는 것이 적합하며, 만약 dfs를 사용한다면 모든 케이스를 둘러보기 때문에 시간초과 혹은 메모리초과에 부딪히게 될 것이다. 3차원 배열을 사용해 상태를 저장하는 것을 떠올렸다면 쉽게 해결할 수 있을 문제.