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

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

그렇게 어렵진 않은 BFS 문제였습니다. 나이트 이동 여부를 체크하기 위해 3차원 체크 배열을 사용하는 것이 문제의 포인트였던 것 같습니다.

 

#include <iostream>
#include <queue>
#define MAX 201
using namespace std;

int map[MAX][MAX];
bool visit[MAX][MAX][MAX]; // x, y 좌표와 나이트 이동 여부를 체크
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int kdx[8] = {2, 2, -2, -2, 1, 1, -1, -1};
int kdy[8] = {1, -1, 1, -1, 2, -2, 2, -2};
int k, w, h;

struct State {
    int x, y, knight, cnt;
};

void BFS(int x, int y, int knight, int cnt) {
    bool flag = false;
    queue<State> q;
    q.push({x, y, knight, cnt}); // 0, 0, 0, 0
    visit[x][y][knight] = true;
    
    while(!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int knight = q.front().knight;
        int cnt = q.front().cnt;
        q.pop();
        
        // 오른쪽 끝에 도달하면 종료
        if(x == h - 1 && y == w - 1) {
            cout<<cnt;
            flag = true;
            break;
        }
        
        // 나이트 이동
        if(knight < k) {
            for(int i = 0; i < 8; i++) {
                int nx = x + kdx[i];
                int ny = y + kdy[i];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if(visit[nx][ny][knight + 1] || map[nx][ny] == 1) continue;
                q.push({nx, ny, knight + 1, cnt + 1});
                visit[nx][ny][knight + 1] = true;
            }
        }
        
        // 일반 이동
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if(visit[nx][ny][knight] || map[nx][ny] == 1) continue;
            q.push({nx, ny, knight, cnt + 1});
            visit[nx][ny][knight] = true;
        }
    }
    
    // 도착지에 갈 수 없는 경우
    if(!flag) cout<<"-1";
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>k>>w>>h;
    
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin>>map[i][j];
        }
    }
    
    BFS(0, 0, 0, 0); // x, y좌표 / 나이트 이동 수 / 총 이동 수
}