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

문제 해결

일반적으로 사용하는 bfs 케이스(상하좌우)에 체스 말 케이스를 추가해서 12가지의 케이스를 고려해서 bfs 코드르 작성하렸다.

여기서 주위해야될 점은 체스말로 이동한 곳은 따로 visit를 해야된다.

visit을 할때 그곳이 k가 0~30번까지 올 수 있기 때문이다. 

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
int map[201][201];
int w,h,k,min_cnt = 987654321;
int case_x[8] = {-2,2,-1,1,-2,2,-1,1};
int case_y[8] = {-1,-1,-2,-2,1,1,2,2};
bool visit[201][201][30];
int case_x2[4] = {0,0,-1,1};
int case_y2[4] = {-1,1,0,0};
bool ck(int y,int x){
    if(x<0 || y<0 || x>=w || y>=h){return false;}
    else if(map[y][x] == 1){return false;}
    else{return true;}
}
void bfs(int y,int x,int cnt_k){
    queue<int> dx,dy,dc,dk;
    int cnt = 0;
    dx.push(x);
    dy.push(y);
    dc.push(cnt);
    dk.push(cnt_k);
    while(!dy.empty()){
        y = dy.front();
        dy.pop();
        x = dx.front();
        dx.pop();
        cnt = dc.front();
        dc.pop();
        cnt_k = dk.front();
        dk.pop();
        if(y == h-1 && x == w-1){
            min_cnt = min(min_cnt,cnt);
            continue;
        }
        else if(visit[y][x][cnt_k]){continue;}
        else{visit[y][x][cnt_k] = true;}
        int temp_x = x,temp_y = y;
        if(cnt_k < k){
            for(int i = 0;i<8;i++){
                x = temp_x+case_x[i];
                y = temp_y+case_y[i];
                if(ck(y,x)){
                    dx.push(x);
                    dy.push(y);
                    dc.push(cnt+1);
                    dk.push(cnt_k+1);
                }
            }
        }
        for(int i = 0;i<4;i++){
            x = temp_x+case_x2[i];
            y = temp_y+case_y2[i];
            if(ck(y,x)){
                dx.push(x);
                dy.push(y);
                dc.push(cnt+1);
                dk.push(cnt_k);
            }
        }
    }
}
int main(void){
    cin >> k;
    cin >> w >> h;
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            cin >> map[i][j];
        }
    }
    memset(visit,false,sizeof(visit));
    bfs(0,0,0);
    if(min_cnt == 987654321){cout << "-1";}
    else{cout << min_cnt;}
}