1600 말이 되고픈 원숭이

1600 말이 되고픈 원숭이

14442번 벽 부수고 이동하기2 와 비슷하다고 느껴져 같은 방법으로 풀어보았다.

기본 아이디어

: visited[ax][ax][k] -> 나이트의 이동처럼 움직이는 경우를 k번 사용한 최소값 저장

1. 상하좌우 4방향과, 나이트의 이동으로 이동 가능한 8가지 경우에 대해 틀을 만든다.

2. x좌표, y좌표, jump사용 횟수를 기록할 Node 구조체를 만든다.

3. bfs를 통해 (0,0)에서 (n,m) 으로 가는 최소값을 찾는다.

4. bfs에서 k번 반복하며, 각각의 visited맵에 jump번 점프한 최소값을 기록해둔다.

5. k개의 visited 배열에서 오른쪽 맨 아래값중 0이 아니면서 가장 작은값을 출력한다. 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
struct Node {
    int x;
    int y;
    int jump;
    Node(int x, int y, int j) :x(x), y(y), jump(j){}
};
 
int k, n, m;
int map[200][200];
int visited[200][200][31];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int nx[] = { -2,-2,-1,-1,1,1,2,2 };
int ny[] = { 1,-1,2,-2,2,-2,1,-1 };
 
void printAll(int a) {
    cout << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << visited[i][j][a] << " ";
        }
        cout << endl;
    }
}
 
void bfs() {
    queue<Node> q;
    q.push(Node(0, 0, 0));// (0, 0)에서 시작
    
    for (int i = 0; i <= k; i++) {
        visited[0][0][i] = 1;
    }
 
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int jump = q.front().jump;
        q.pop();
 
        for (int i = 0; i <= k; i++) {
            //상하좌우
            for (int j = 0; j < 4; j++) {
                int ax = x + dx[j];
                int ay = y + dy[j];
                if (ax >= 0 && ay >= 0 && ax < n&&ay < m) {
                    if (map[ax][ay] == 1) continue;
 
                    if (visited[ax][ay][jump] == 0 || visited[ax][ay][jump] > visited[x][y][jump] + 1) {
                        q.push(Node(ax, ay, jump));
                        visited[ax][ay][jump] = visited[x][y][jump] + 1;
                    }
                }
            }
            //나이트 이동
            if (jump < k) {
                for (int j = 0; j < 8; j++) {
                    int ax = x + nx[j];
                    int ay = y + ny[j];
                    if (ax >= 0 && ay >= 0 && ax < n&&ay < m) {
                        if (map[ax][ay] == 1) continue;
                        
                        if (visited[ax][ay][jump + 1] == 0 || visited[ax][ay][jump + 1] > visited[x][y][jump] + 1) {
                            q.push(Node(ax, ay, jump + 1));
                            visited[ax][ay][jump + 1] = visited[x][y][jump] + 1;
                        }
                    }
                }
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin >> k >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    bfs();
    int res = 1e9;
    for (int i = 0; i <= k; i++) {
        if (visited[n - 1][m - 1][i] != 0) {
            res = min(res, visited[n - 1][m - 1][i]);
        }
    }
    if (res == 1e9) cout << -1 << endl;
    else cout << res - 1 << endl;
 
    return 0;
}