BOJ 1600 말이 되고픈 원숭이

 

백준 BOJ 1600 C++

말이 되고픈 원숭이

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

 

1) BFS 문제

2) #14442 벽 부수고 이동하기2 (https://www.acmicpc.net/problem/14442) 와 비슷한 문제라고 생각했다. 

    #14442와 마찬가지로 주어진 K만큼 특별한 이동(말의 이동처럼)을 할 수 있다.(hx, hy)

    cnt가 K보다 작을 때는 hx, hy를 이용하여 이동하는 경우를 큐에 push, 그리고 K와 관계없이 dx,dy를 이용하여 인접한 이동에 대해 큐에 push했다.

3) 원숭이의 도착 지점이 (H,W)이므로, 도착 지점 도달 시 가능한 ans의 최솟값을 비교하여 update한다.

4) 내가 실수했던 지점은, 47line에서 check[nx][ny][cnt+1] -> check[nx][ny][cnt]으로 cnt를 update하지 않아 메모리 초과가 발생했다. 

   

/**
 * 200605
 * BOJ 1600 말이 되고픈 원숭이
 * BFS
 * */

#include <iostream>
#include <queue>
using namespace std;

int K, W, H;
int map[205][205];
int check[205][205][35];

int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};

int hx[8]={-2,-2,-1,-1,1,1,2,2};
int hy[8]={-1,1,-2,2,-2,2,-1,1};

struct info{
    int x, y, cnt;
};

int ans = 987654321;

void solve(){
    queue <info> q;
    q.push({1,1,0});
    check[1][1][0]=0;

    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop();

        if(x==H && y==W){
            if(ans>check[x][y][cnt]) ans = check[x][y][cnt];
        }

        if(cnt<K){
            for(int i=0; i<8; i++){
                int nx = x + hx[i];
                int ny = y + hy[i];
                if(0<nx && nx<=H && 0<ny && ny<=W){
                    if(map[nx][ny]==0 && check[nx][ny][cnt+1]==0){
                        check[nx][ny][cnt+1] = check[x][y][cnt]+1;
                        q.push();
                    }
                }
            }
        }

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<nx && nx<=H && 0<ny && ny<=W){
                if(map[nx][ny]==0 && check[nx][ny][cnt]==0){
                    check[nx][ny][cnt] = check[x][y][cnt]+1;
                    q.push();
                }
            }
        }
    }

    if(ans==987654321) ans = -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> K >> W >> H;
    for(int i=1; i<=H; i++)
        for(int j=1; j<=W; j++)
            cin >> map[i][j];

    solve();
    cout << ans << '\n';

    return 0;
}