[백준][1600번] 말이 되고픈 원숭이 [cpp, c++]

백준 1600 말이 되고픈 원숭이

• BFS를 이용한 문제이다.
• 말이 이동하는 경우, 원숭이가 이동하는 경우를 모두 계산해서 풀면 된다.
• https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

• 풀이 방법

  1) 3차원 배열을 이용해서, 말처럼 이동하는 경우를 고려해야한다.
  2) 말 처럼 이동하는 경우만 고려하면, 일반 BFS와 같다.

 
#include <iostream>
#include <queue>
using namespace std;
typedef struct _point {
    int x;
    int y;
    int knight;
    int cnt;
}point;
queue<point> q;
int K, W, H; // 정수 K, 가로길이 W, 세로길이 H가 주어진다. 
int map[200][200];
bool visited[201][201][31];
int horse_x[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };
int horse_y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int nx[4] = { 1,0,-1,0 };
int ny[4] = { 0,1,0,-1 };
void input_data() {
    cin >> K >> W >> H;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> map[i][j];
        }
    }
}
 
int bfs() {
    q.push({ 0,0,0,0 });
    visited[0][0][0] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int kight = q.front().knight;
        int cnt = q.front().cnt;
        q.pop();
 
        if (x == H - 1 && y == W - 1) {
            return cnt;
        }
        if (kight < K) { //말 bfs
            for (int i = 0; i < 8; i++) {
                int hx = horse_x[i] + x;
                int hy = horse_y[i] + y;
                if (hx < 0 || hx >= H || hy < 0 || hy >= W) continue;
                if (visited[hx][hy][kight + 1] == true || map[hx][hy] == 1) continue; // 방문 했던 곳 or 장애물
                visited[hx][hy][kight + 1] = true;
                q.push({ hx,hy,kight + 1,cnt + 1 });
            }
        }
 
        for (int i = 0; i < 4; i++) { //원숭이 bfs
            int dx = nx[i] + x;
            int dy = ny[i] + y;
            if (dx < 0 || dx >= H || dy < 0 || dy >= W) continue;
            if (visited[dx][dy][kight] == true || map[dx][dy] == 1) continue; // 방문 했던 곳 or 장애물
            visited[dx][dy][kight] = true;
            q.push({ dx,dy,kight,cnt + 1 });
        }
    }
    return -1;
}
 
void sol() {
    input_data();
    cout << bfs() << "\n";
}
 
 
 
int main(void) {
    sol();
    return 0;
}