백준 1600번 - 말이 되고픈 원숭이

백준 1600번 - 말이 되고픈 원숭이

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

문제

• 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다.

• 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다.

• 다음그림에 말(H)의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다.(참고로 말은 장애물을 뛰어넘을 수 있다.)

  . x . x .
  x . . . x
  . . H . .
  x . . . x
  . x . x .

• 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력치가 딸려서 총 K번만 저렇게 움직일 수 있고, 그 외에는 그냥 동서남북방향으로 1칸씩만 움직일 수밖에 없다.

• 이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽위에서 시작해서 맨 오른쪽아래까지 가야한다. 동서남북으로 한번 움직이던, 말의 움직임으로 한번 움직이던, 모두 한번의 동작으로 친다.

• 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오..

입력

• 첫째 줄에 자연수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다.

• 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 움직일 수 없다.

• 시작점과 도착점은 항상 평지이다.

• W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

출력

• 첫째 줄에 원숭이의 동작수의 최소값을 출력한다.

• 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.

접근

• BFS로 푼다.

• 좌표(x, y)와 말 처럼 움직일 수 있는 수(k), 현재 움직인 횟수(cnt)를 담는 구조체를 만든다.

• 최단거리를 우선으로 탐색하는 BFS의 특성상 목표 지점에 도달했을 때의 cnt값이 최단거리이다.

• visited 플래그 배열은 x, y 좌표 뿐만 아니라, 말처럼 움직일 수 있는 수(k)까지 담아야 한다.

1
5 5
0 0 0 1 1
0 0 0 1 1
0 0 0 1 1
1 1 1 1 1
1 1 1 0 0

• 위의 예시에서는 답이 6이 나와야 한다. 그러나 visited 플래그 배열에서 x, y 좌표만 체크하게 되면, 말 처럼 이동할 수 있는 횟수를 이미 사용한 게 되어버려 이동할 수 없다고 나온다.

C++ Code

#include <cstdio>
#include <queue>
#include <algorithm>
​
using namespace std;
​
int k;
int w, h;
int map[201][201];
bool visited[201][201][31] = { false };
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int kdx[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int kdy[] = { 1, -1, 1, -1, 2, -2, 2, -2 };
​
struct pos {
    int x;
    int y;
    int k;
    int cnt;
    pos(int a, int b, int c, int d) : x(a), y(b), k(c), cnt(d) {}
};
​
int bfs(int k) {
    queue<pos> q;
    q.push(pos(0, 0, k, 0));
​
    while (!q.empty()) {
        pos cur = q.front();
        q.pop();
​
        if (cur.x < 0 || cur.y <0 || cur.x >= w || cur.y >= h) continue;
        if (map[cur.y][cur.x]) continue;
​
        if (cur.x == w - 1 && cur.y == h - 1) {
            return cur.cnt;
        }
​
        if (visited[cur.y][cur.x][cur.k]) continue;
        visited[cur.y][cur.x][cur.k] = true;
        
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            q.push(pos(nx, ny, cur.k, cur.cnt + 1));
        }
​
        if (cur.k == 0) continue;
        for (int i = 0; i < 8; i++) {
            int nx = cur.x + kdx[i];
            int ny = cur.y + kdy[i];
            q.push(pos(nx, ny, cur.k - 1, cur.cnt + 1));
        }
    }
​
    return -1;
}
​
int main(void) {
    scanf("%d %d %d", &k, &w, &h);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            scanf("%d", &map[i][j]);
        }
    }
​
    printf("%d\n", bfs(k));
​
    return 0;
}