[백준 1600] 말이 되고픈 원숭이_bfs(c++)

[문제]

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

1600번: 말이 되고픈 원숭이

[접근방법]

1. 원숭이가 인접한 4방향으로 움직이는것과 말의 움직임으로 한번 움직이는 것을 모두 한번의 동작으로 친다 <- 이동하는 방법의 가중치가 1로 같다는 점과 4방향으로 움직이면서 탐색해야 하는 것을 보고 bfs라고 판단했다.

2. queue에 좌표(x,y)와 cnt(원숭이가 목적지까지 움직인 횟수를 저장하는 변수), hor(말처럼 이동할 수 있는 횟수를 저장)

3. 방문체크를 평소와 같이 check[nx][ny]로 하려고 했다. <-이게 잘못된 방법이었음

---

[문제풀이]

1.원숭이가 시작점(0,0)에서(고정) (h-1, w-1)로 도착하는 방법의 가지수를 구하라고 했음

2. 큐 안에 이동횟수(cnt)를 안고 다니면 쉽게 구할 수 있다.

3. 하지만 여기서는 말처럼 이동할 수 있다는 조건이 있으므로 일반 bfs처럼 방문체크를 하면 안되는 것을 간과 ㅠㅠ

4. 2차원 배열로 방문체크를 하게 되면 말의 횟수 1번써서 방문한 A점을 말의 횟수 2(3,4,5...)번써서는 방문할 수 없게 되기 때문에 방문의 경우수가 제대로 구해지지 않게 됨

5. 따라서 3차원 배열로 [말의 이동횟수의 크기][x][y] 을 만들어주어야 한다.

6. 말의 횟수에 따라서 방문한 x,y를 따로 체크하기 위해서다.

 

[전체코드]

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct Pos {
    int x;
    int y;
    int cnt;//이동한 횟수
    int hor; //말처럼이동할 수 있는 횟수
};
 
int dx[] = {2,2,-2,-2,1,1,-1,-1,  0,0,-1,1}; //8~11까지는 말이 아닌 원숭이가 가는 방법
int dy[] = {-1,1,-1,1,2,-2,2,-2,  1,-1,0,0};//말로 이동할 수 있는 경우의 수
 
int k, w, h;
int result = 123594387;
 
int bfs(queue<Pos> q, bool check[200][200][32], int ** map) {
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int c = q.front().cnt;
        int horse = q.front().hor;
        if (x == w-1 && y == h-1) {
            //if (result > c) result = c;
            return c;
        }
        q.pop();
        //[x][y] = true;
        
        //말처럼 이동하는 경우
        if(horse < k) {
            for (int i = 0; i < 8; i++) { //이 방향으로 가는것을 k번만큼만 한다.
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < w && ny < h) {
                    if (check[nx][ny][horse + 1] == false && map[nx][ny] == 0) {
                        check[nx][ny][horse + 1] = true;
                        q.push({ nx, ny, c + 1 , horse + 1 });
                    }
                }
            }
        }
        //원숭이로 이동하는 경우
        for (int i = 8; i < 12; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < w && ny < h) {
                if (check[nx][ny][horse] == false && map[nx][ny] == 0) {
                    check[nx][ny][horse] = true;
                    q.push({ nx, ny, c + 1 , horse });
                }
            }
        }
    }
    //result = -1;
    return -1; //못가는 경우
}
 
int main() {
    cin >> k;//원숭이가 말처럼 움직일 수 있는 횟수
    cin >> w >> h; //가로, 세로
 
    queue<Pos> q; //원숭이가 이동할 수 있도록 하는 큐
    Pos pos = {0,0,0};//원숭이의 처음 시작점은 0,0 이동횟수는 0
    q.push(pos);
 
    int** map = new int* [w];
    memset(map, 0, sizeof(w));
 
    bool check[200][200][32];
 
    for (int i = 0; i < w; i++) {    
        map[i] = new int[h];
        memset(map[i], 0, sizeof(int) * h);
    }
 
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> map[j][i];
        }
    }
 
    cout << bfs(q, check, map) << "\n";
    return 0;