[ 백준 BOJ ] 1600번 - 말이 되고픈 원숭이(C++)

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

 

생각 흐름

• 일반적인 bfs 문제이지만, 같은 위치에 도착해도 k를 사용한 개수가 다를 수 있으므로 방문 여부를 checked[y][x][k]와 같이 설정해야한다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int K, N, M;
vector<vector<int>> m;
bool checked[200][200][30];
int mx[4] = {1,-1,0,0};
int my[4] = {0,0,1,-1};
int hx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int hy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

int answer;

int bfs(){
    //cost, k, y, x
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push({{0,0},{0,0}});
    while(!q.empty()){
        int cost = q.front().first.first;
        int k = q.front().first.second;
        int y = q.front().second.first;
        int x = q.front().second.second;
        q.pop();
        
        if(y==N-1 && x == M-1) {
            return cost;
        }
        
        for(int i = 0; i<4; i++){
            int dx = x+mx[i];
            int dy = y+my[i];
            
            if(dx>=M || dx<0 || dy>=N || dy<0 || m[dy][dx]==1 || checked[dy][dx][k]) continue;
            
            q.push({{cost+1, k},{dy, dx}});
            checked[dy][dx][k]=true;
        }
        if(k<K){
            for(int i = 0; i<8; i++){
                int dx = x+hx[i];
                int dy = y+hy[i];
                
                if(dx>=M || dx<0 || dy>=N || dy<0 || m[dy][dx]==1 || checked[dy][dx][k+1]) continue;
                
                q.push({{cost+1, k+1},{dy, dx}});
                checked[dy][dx][k+1]=true;
            }
        }
    }
    
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>K>>M>>N;
    for(int i = 0; i<N; i++){
        vector<int> v;
        for(int j = 0; j<M; j++){
            int tmp;
            cin>>tmp;
            
            v.push_back(tmp);
        }
        m.push_back(v);
    }
    
    cout<<bfs()<<endl;
    
    return 0;
}