BOJ 1600 말이 되고픈 원숭이 [ CPP, Algorithm, BFS ]

문제 풀이
일반적인 BFS 방식이다.

먼저 말처럼 이동할 수 있는 횟수가 정해져 있는데 이걸 큐에 저장하면서 말의 능력을 몇번 썼는지 확인하며 말의 능력을 쓸 수 있다면 먼저 말의 능력을 쓴다. 그리고 말의 능력을 썼을때와 쓰지 않았을때, 또 말의 능력을 쓴 횟수가 다를때의 visited는 다르기 때문에 3차원 배열을 이용해서 말의 방문 확인을 한다면 쉽게 풀 수 있다

 

 

#include <bits/stdc++.h>
using namespace std;
int graph[200][200];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int dxHorse[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dyHorse[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int visited[200][200][31];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int k,H,W;
    cin >> k >> W >> H ;
    for(int i=0; i < H; i++){
        for(int j=0; j < W; j++){
            cin >> graph[i][j];
        }
    }

    // {좌표}, {이동거리, 말처럼 이동한 이동거리}
    queue<pair<pair<int,int>,pair<int,int>>> Q;
    Q.push({{0,0},{0,0}});
    visited[0][0][0]=1;
    while(!Q.empty()){
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int dist = Q.front().second.first;
        int horseCnt = Q.front().second.second;
        Q.pop();
        if(x == H - 1 && y == W - 1){
            cout << dist;
            return 0;
        }
        if(horseCnt<k){
            for(int dir=0;dir<8;dir++){
                int nx = x + dxHorse[dir];
                int ny = y + dyHorse[dir];
                if(nx < H && nx >= 0 && ny < W && ny >= 0){
                    if(graph[nx][ny]==0 && !visited[nx][ny][horseCnt+1]){
                        visited[nx][ny][horseCnt+1]=1;
                        Q.push({{nx,ny},{dist+1,horseCnt+1}});
                    }
                }
            }
        }
            for(int dir=0;dir<4;dir++){
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if(nx < H && nx >= 0 && ny < W && ny >= 0){
                    if(graph[nx][ny]==0 && !visited[nx][ny][horseCnt]){
                        visited[nx][ny][horseCnt]=1;
                        Q.push({{nx,ny},{dist+1,horseCnt}});
                    }
                }

            }
    }
    cout << "-1";
}