(BOJ) 1600 풀이

1600

#include<bits/stdc++.h>
using namespace std;
typedef struct _XYZ{
    int x;
    int y;
    int z;
}xyz;
int dx[]={-1,0,1,0,-1,-2,-2,-1,1,2, 2, 1};
int dy[]={0,1,0,-1,-2,-1, 1, 2,2,1,-1,-2};
int board[202][202];
int visited[202][202][32];
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    int K,W,H,flag=0;
    xyz v;
    queue<xyz> Q;
    cin >> K;
    cin >> W >> H;
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            cin >> board[i][j];
        }
    }
    Q.push({1,1,K});
    while(!Q.empty()){
        v=Q.front();Q.pop();
        if(v.x==H&&v.y==W){
            flag=1;
            printf("%d\n",visited[H][W][v.z]);
            break;
        }
        for(int i=0;i<(v.z>0?12:4);i++){
            int nx=v.x+dx[i];
            int ny=v.y+dy[i];
            int nz=i<4?v.z:v.z-1;
            if(nx<1||nx>H||ny<1||ny>W||visited[nx][ny][nz]!=0||board[nx][ny]==1)continue;
            visited[nx][ny][nz]=visited[v.x][v.y][v.z]+1;
            Q.push({nx,ny,nz});
        }
    }
    if(!flag){
        printf("-1\n");
    }
}

원숭이가 말처럼 이동할 수 있는 K 번의 기회가 있다.

큐에 이 기회를 같이 넣으면서 만약 1번 이상이면,

원숭이 상하좌우 4번 + 말처럼 이동 8번 만큼 반복문을 돈다.

원숭이로 이동할 때는 기회 (z) 를 그대로 visited 배열과 큐에 반영하고

말처럼 이동할 때는 기회를 하나 감소시켜 지금까지 visited[x][y][z] 만큼 이동한 거리 +1 을 visited[nx][ny][z-1] 에 넣어 기회가 z-1 일 때 이동거리에 반영할 수 있도록 짜야한다.