BOJ 1600 - 말이 되고픈 원숭이

BOJ 1600 - 말이 되고픈 원숭이

[분류 - BFS]

 

[풀이]

  말처럼 뛰는 동작은 k를 정확히 1만큼을 올리기 때문에 k+1과 k는 인접해있다. 
  따라서 k+1번째에 특정 좌표 (y, x)에 도달했다면 그 값이 곧 최소 동작이 된다.

 

vi[k][y][x] - y행 x열에 k번만 말처럼 뛰어서 도달할 수 있는 동작 수의 최소값

 

  BFS 특성상 진행하려는 방향에 대해 정확히 1만큼 증가시키고 vi[k+1][y][x]에 도달할 수 있는 위치가 (y1, x1), (y2, x2)일 때,

1. vi[k][y1][x1] > vi[k][y2][x2]
  BFS 큐에 들어가는 좌표는 (y2, x2)가 더 우선순위를 가진다.

2. vi[k][y1][x1] <= vi[k][y2][x2]
  BFS 큐에 들어가는 좌표는 (y1, x1)가 더 우선순위를 가진다.

따라서 최초 방문은 곧 최소 동작 수를 나타냄을 알 수 있다.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX_H = 200, MAX_K = 51;
struct _d { int k, y, x; };
int main() {
    int i, j, K, H, W, vi[MAX_K][MAX_H][MAX_H] = {}, b[MAX_H][MAX_H], dy[2][8] = { {0,0,1,-1}, {-1,-2,-2,-1,1,2,2,1} }, dx[2][8] = { {1,-1,0,0}, {-2,-1,1,2,2,1,-1,-2} }, n[] = { 4,8 }, answer = 1e9;
    queue<_d> q;
    scanf("%d%d%d", &K, &W, &H);
    for (i = 0; i < H; i++) for (j = 0; j < W; j++)
        scanf("%d", &b[i][j]);
    vi[K][0][0] = 1;
    q.push({ K, 0, 0 });
    while (!q.empty()) {
        auto u = q.front(); q.pop();
        if (u.y == H - 1 && u.x == W - 1)
            answer = min(answer, vi[u.k][u.y][u.x] - 1);
        for (i = 0; i < 2; i++) {
            int tk = u.k - i;
            if (u.k - i >= 0)
                for (j = 0; j < n[i]; j++) {
                    int ty = u.y + dy[i][j], tx = u.x + dx[i][j];
                    if (0 <= ty && ty < H && 0 <= tx && tx < W && vi[tk][ty][tx] == 0 && b[ty][tx] == 0) {
                        vi[tk][ty][tx] = vi[u.k][u.y][u.x] + 1;
                        q.push({ tk, ty, tx });
                    }
                }
        }
    }
    printf("%d", answer == 1e9 ? -1 : answer);
    return 0;
}