말이 되고픈 원숭이 (feat. 백준, 1600번)

말이 되고픈 원숭이
https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int K, W, H, dx[4], dy[4], hx[8], hy[8], arr[201][201];
int visit[201][201][31];
int bfs(register int x, register int y){
    register int k = 0, ans = 99999999;
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(x, y, k));
    visit[x][y][k] = 1;
    while(!q.empty()){
        auto p = q.front(); q.pop();
        x = get<0>(p), y = get<1>(p), k = get<2>(p);
        if(x == H && y == W){
            for(register int i = 0; i <= K; ++i)
                if(visit[x][y][i])
                    ans = min(ans, visit[x][y][i]);
        }
        // 원숭이
        for(register int d = 0, nx, ny; d < 4; ++d){
            nx = x + dx[d], ny = y + dy[d];
            if(1 <= nx && nx <= H && 1 <= ny && ny <= W && !arr[nx][ny] && !visit[nx][ny][k])
                visit[nx][ny][k] = visit[x][y][k] + 1, q.push(make_tuple(nx, ny, k));
        }
        // 말
        if(k < K)
            for(register int d = 0, nx, ny; d < 8; ++d){
                nx = x + hx[d], ny = y + hy[d];
                if(1 <= nx && nx <= H && 1 <= ny && ny <= W && !arr[nx][ny] && !visit[nx][ny][k + 1])
                    visit[nx][ny][k + 1] = visit[x][y][k] + 1, q.push(make_tuple(nx, ny, k + 1));
            }
    }
    if(ans == 99999999)
        ans = 0;
    return ans - 1;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(visit, 0, sizeof(visit));
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    hx[0] = hx[7] = -2, hx[1] = hx[6] = -1, hx[2] = hx[5] = 1, hx[3] = hx[4] = 2;
    hy[0] = hy[3] = 1, hy[1] = hy[2] = 2, hy[4] = hy[7] = -1, hy[5] = hy[6] = -2;
    cin >> K >> W >> H;
    for(register int h = 1, w; h <= H; ++h)
        for(w = 1; w <= W; ++w)
            cin >> arr[h][w];
    cout << bfs(1, 1);
    return 0;
}
// *&)*@*

 

1. 까다로운 bfs 문제입니다.
2. K번 말이 될 수 있기 때문에 K번만큼의 체킹 배열이 더 필요로 합니다. 또한 (X,Y) 지점에 도달했을때 0부터 K번 말을 사용한 모든 경우 중 답을 찾아야 합니다.
3. 그 외에는 기존 bfs 문제들과 동일한 유형입니다.