백준 1600번 : 말이 되고픈 원숭이 - 상태 추가 BFS

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

1600번: 말이 되고픈 원숭이

1. 문제설명

일반적인 BFS문제는 상하좌우로 네칸만 움직인다.

이 문제는 원숭이가 평소에는 상하좌우로 네칸을 움직일 수 있다가

K번의 기회로 말처럼 더 넓은 범위를 움직일 수 있다.

 

이런 문제를 표현하기 위해서는 최대 K번 말처럼 움직일 수 있으므로

현재까지 원숭이가 총 몇 번 말처럼 움직였는지 상태를 저장해줄 필요가 있다.

그래서 이러한 문제 유형을 나는 상태 추가 BFS라고 부르기로 했다.

그냥 저 혼자 부르는 거니까 다른데 가서 유식한 척 말하시면 안됩니다.

 

 

 

2. 상태추가?

왜 상태추가라고 하냐면

보통 일반적으로 BFS를 돌 때는

x,y 좌표를 방문했는지 여부를 저장하면서 중복된 행동을 하지 않도록 합니다.

 

이 문제도 단지 x,y좌표를 방문했는지 여부와 동일하게

x,y좌표 방문 여부 + '말처럼 움직인 횟수' 라는 상태가 추가되어

중복된 행동을 하지 않으면서 BFS를 돈다고 생각하면 편합니다.

 

 

그리고 또한 이 문제를 왜 BFS로 해결 할 수 있냐면

원하는 답이 원숭이가 총 몇번 움직이는 행동을 했는 지 구하는 것이기 때문에

말처럼 움직이든 원숭이처럼 움직이든 특정 행동엔 관심없고

움직임 단계별로 일정하게 증가시키면서 답을 구하면 되기 때문에

너비우선탐색으로 해결 할 수 있습니다.

 

 

 

---

 

 

3.문제풀이코드 C++

 

#include <bits/stdc++.h>

using namespace std;

struct Position {
    int x, y, k, d;

    Position(int a, int b, int c, int dd) {
        x = a, y = b, k = c, d = dd;
    }
};

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
//horse
int hdx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int hdy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

queue<Position> Q;

int K, W, H;
int arr[203][203];
bool vis[203][203][32];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> K >> W >> H;

    // 행H , 열W
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> arr[i][j];
        }
    }

    Q.push({0, 0, 0, 0});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

        if (cur.x == H - 1 && cur.y == W - 1) {
            cout << cur.d << '\n';
            return 0;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (vis[nx][ny][cur.k] || arr[nx][ny] == 1) continue;

            vis[nx][ny][cur.k] = 1;
            Q.push({nx, ny, cur.k, cur.d + 1});
        }

        if (cur.k + 1 <= K) {
            for (int i = 0; i < 8; i++) {
                int nx = cur.x + hdx[i];
                int ny = cur.y + hdy[i];

                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (vis[nx][ny][cur.k + 1] || arr[nx][ny] == 1) continue;

                vis[nx][ny][cur.k + 1] = 1;
                Q.push({nx, ny, cur.k + 1, cur.d + 1});
            }
        }
    }

    cout << -1 << '\n';


    return 0;
}

백준 1600번