[BOJ # 1600] 말이 되고픈 원숭이

주어진 문제는 위와 같다. 2차원 행렬에서 (0, 0) -> (M - 1, N - 1) 까지의 최단 거리를 구하는 문제에 특별한 이동 방식이 추가된 형태이다. 특별한 이동 방식은 체스에서 나이트가 움직이는 방식과 같고 문제에서 정의한 K 만큼 이러한 방식으로 이동할 수 있다.

 

일반적인 BFS 문제는 큐를 사용해 각각의 이동으로 인한 현재 위치를 저장하고 그 위치가 목적지에 도달하면 종료하게 된다. 이 때, 동일한 위치에 대해서 재방문을 할 필요가 없기 때문에 각 위치 (x, y) 의 방문 여부를 저장한다. 이 문제는 이에 더해 그 위치까지 몇 번의 이동 능력을 사용했는 지가 중요하기 때문에 (x, y) 위치 + 이동 능력 사용 횟수 를 기준으로 방문 여부를 체크하면 해결할 수 있다.

 

이러한 풀이로 작성한 소스 코드는 다음과 같다.

 

#include <iostream>
#include <queue>

using namespace std;

const int MAX_SIZE = 200;

struct POINT {
    int r, c;
    int horse, cnt;

    POINT(int r, int c, int horse, int cnt) : r(r), c(c), horse(horse), cnt(cnt) {}
};

int dr[4] = {1, 0, -1, 0}, dc[4] = {0, 1, 0, -1};
int hr[8] = {-1, -2, -2, -1, 1, 2, 2, 1}, hc[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

int N, M, K;
int map[MAX_SIZE][MAX_SIZE];
bool vis[MAX_SIZE][MAX_SIZE][31];

void input() {
    cin >> K;
    cin >> M >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
}

int solve() {
    queue<POINT> que;

    que.push(POINT(0, 0, 0, 0));
    while (que.size()) {
        POINT top = que.front();
        que.pop();

        if (top.r == N - 1 && top.c == M - 1) {
            return top.cnt;
        }

        if (vis[top.r][top.c][top.horse])
            continue;
        vis[top.r][top.c][top.horse] = true;

        if (top.horse < K) {
            for (int k = 0; k < 8; k++) {
                int nr = top.r + hr[k], nc = top.c + hc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M)
                    continue;
                if (map[nr][nc] || vis[nr][nc][top.horse + 1])
                    continue;
                que.push(POINT(nr, nc, top.horse + 1, top.cnt + 1));
            }
        }
        for (int k = 0; k < 4; k++) {
            int nr = top.r + dr[k], nc = top.c + dc[k];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M)
                continue;
            if (map[nr][nc] || vis[nr][nc][top.horse])
                continue;
            que.push(POINT(nr, nc, top.horse, top.cnt + 1));
        }
    }

    return -1;
}

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

    input();
    cout << solve();

    return 0;
}

 

solve() 함수에서 기존 BFS 소스 코드와 차이점이 있다면, if (top.horse < K) 로 시작되는 분기문이다. POINT 구조체의 horse 는 현재까지 이동 능력의 사용 횟수이며 이 횟수가 K 보다 작다면 특별한 이동 방식으로 이동할 수 있도록 한다. 또한, bool 타입 3차원 행렬 vis 에서 마지막 인덱스로 horse 값을 사용해 해당 위치까지 가는 동안 사용한 이동 능력의 횟수를 확인해 재방문을 막는다.