[백준] 1600 말이 되고픈 원숭이

처음봤을 때 DP로 풀다가 실패해서 안푼 문제다

그러다가 오늘 다시 다익스트라로 풀었다

다익스트라로 생각하면 쉽게 풀 수 있다

내가 K번 말처럼 뛸 수 있으므로 cnt =K로 하고 cnt를 저장해서 가져다니면 된다

pq에 넣고 다니면 끝이다..!

아 근데 이문제 가로 세로 잘봐야한다 ㅋㅋㅋ

그리고 다들 오타가 안나도록 조심.. n,m,= 이런거...

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int inf = 1e9;
int k, n, m;
int arr[202][202], d[202][202][33];
bool check[202][202][33];
 
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int ddx[8] = { -2,-1,1,2,2,1,-1,-2 };
int ddy[8] = { 1,2,2,1,-1,-2,-2,-1 };
 
int main() {
    for (int i = 0; i < 201; i++) {
        for (int j = 0; j < 201; j++) {
            for (int k = 0; k < 31; k++) {
                d[i][j][k] = inf;
            }
        }
    }
    scanf(" %d %d %d", &k, &m, &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %d", &arr[i][j]);
        }
    }
 
    d[0][0][0] = 0;
    priority_queue<pair<pair<int, int>, pair<int, int>>> pq;
    pq.push({ {0,k},{0,0} });
    while (!pq.empty()) {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        int cost = -pq.top().first.first;
        int cnt = pq.top().first.second;
        pq.pop();
 
        if (check[x][y][cnt]) continue;
        check[x][y][cnt] = true;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int ncost = cost + 1;
            if (arr[nx][ny]) continue;
            if (0 <= nx && nx < n && 0 <= ny &&ny < m) {
                if (d[nx][ny][cnt] > ncost) {
                    d[nx][ny][cnt] = ncost;
                    pq.push({ { -ncost,cnt },{ nx,ny } });
                }
            }
        }
 
        if (cnt == 0) continue;
        for (int i = 0; i < 8; i++) {
            int nx = x + ddx[i];
            int ny = y + ddy[i];
            if (arr[nx][ny]) continue;
            int ncost = cost + 1;
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (d[nx][ny][cnt - 1] > ncost) {
                    d[nx][ny][cnt - 1] = ncost;
                    pq.push({ {-ncost,cnt - 1},{nx,ny} });
                }
            }
        }
    }
 
    int ans = inf;
    for (int i = 0; i <= k; i++) ans = min(ans, d[n - 1][m - 1][i]);
    printf("%d\n", ans == inf ? -1 : ans);
}