백준 1600: 말이 되고픈 원숭이

백준 1600: 말이 되고픈 원숭이

1600번: 말이 되고픈 원숭이

 

제한시간 : 2초

메모리 : 256MB

 

처음엔 DP 문제인줄 알고 DFS를 이용해서 풀려했지만 풀리지 않았고 BFS로도 잘 풀리지 않았다. 결국에는 구글링으로 해결했다. 문제를 처음봤을 때 K의 갯수가 제한이 필요한가 의문이 들었었는데 구글링이 결국 답을 알려주었고, BFS 때 사용하는 VISIT와 K를 잘 조합하여 이용해야 했었다. 목적지까지 가는데 최소한의 길로 이동해야하는 모든 경우의 수를 얻어야하는데 BFS로 접근을하면 가장 먼저 도달하는 경우가 최소한의 거리가 되는 것이다. 여기서 이동할 때 주의해야 할 점은 visit이다. 말처럼 이동할 수 있는 경우를 모두 체크해주어야한다. 같은 좌표로 이동하더라도 k의 사용횟수에 따라 이동 유무를 알 수 있어야하기 때문이다. 그러기때문에 visit는 3차원 배열로 선언하여 사용했다.

 

1. BFS를 사용하여 최소한의 거리를 접근

2. 다음 격자판으로 이동할 때 K의 사용횟수와 이동할 수 있는 공간을 체크

3. 장애물로는 못움직인다.

4. K횟수가 같은데 이미 방문한 곳이면 이동하면 안된다.

5. 이동할 때 마다 경로 1 추가

6. 끝점에 도달하면 경로 값을 출력한다.

 

#include<iostream>
#include<cstring>
#include<queue>

#define MAX_SIZE 200

using namespace std;

typedef struct pos{
    int y;
    int x;
    int k;
    int route;
}pos;

int field[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE][31];

int w, h;
int res = -1;
int dirW[] = {1,-1,0,0};
int dirH[] = {0,0,1,-1};
int horseW[] = {1,2,1,2,-1,-2,-1,-2};
int horseH[] = {2,1,-2,-1,2,1,-2,-1};

queue<pos> monkey;

void bfs(){
    int x, y, k, route;
    int dx, dy;
    while(!monkey.empty()){
        x = monkey.front().x;
        y = monkey.front().y;
        k = monkey.front().k;
        route = monkey.front().route;
        monkey.pop();
        if(x == w-1 && y == h-1){
            res = route;
            return;
        }
        for(int i = 0; i < 4; i++){
            dx = x + dirW[i];
            dy = y + dirH[i];
            if(dx < 0 || dx >= w || dy < 0 || dy >= h) continue;
            if(field[dy][dx] == 1) continue;
            if(visit[dy][dx][k]) continue;
            visit[dy][dx][k]= true;
            monkey.push({dy, dx, k, route+1});
        }
        if(k > 0){
            for(int i = 0; i < 8; i++){
                dx = x + horseW[i];
                dy = y + horseH[i];
                if(dx < 0 || dx >= w || dy < 0 || dy >= h) continue;
                if(field[dy][dx] == 1) continue;
                if(visit[dy][dx][k-1]) continue;
                visit[dy][dx][k-1] = true;
                monkey.push({dy, dx, k-1, route+1});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    cin >> w >> h;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> field[i][j];
        }
    }
    monkey.push({0,0,k,0});
    bfs();
    cout << res;
    return 0;
}