[Algorithm] 백준 1600 말이 되고픈 원숭이 - C++, BFS

1600번: 말이 되고픈 원숭이

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int moveY[] = { 0, 0, 1, -1 };
int moveX[] = { 1, -1, 0, 0 };
pair<int, int> horseMove[] = { {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, 
                               {1, -2}, {2, -1}, {2, 1}, {1, 2} };
int k, w, h;
int map[201][201];
bool visit[201][201][31];

bool IsOut(int y, int x){
    if(x < 0 || y < 0 || x >= w || y >= h)
        return true;
    if(map[y][x] == 1)
        return true;
    return false;
}

bool SearchCount(){
    queue<pair<pair<int, int>, pair<int, int>>> q;
    q.push({{0, 0}, {0, 0}});

    while(!q.empty()){
        int curK = q.front().first.first;
        int curCount = q.front().first.second;
        int curY = q.front().second.first;
        int curX = q.front().second.second;
        q.pop();

        // if now on finish
        if(curY == h-1 && curX == w-1){
            cout << curCount << '\n';
            return true;
        }

        // can horse movement
        if(curK < k){
            for(int i = 0; i < 8; i++){
                int nextY = curY + horseMove[i].first;
                int nextX = curX + horseMove[i].second;

                if(IsOut(nextY, nextX)) continue;
                if(visit[nextY][nextX][curK+1]) continue;

                q.push({{curK+1, curCount+1}, {nextY, nextX}});
                visit[nextY][nextX][curK+1] = true;
            }
        }

        // normal movement
        for(int i = 0; i < 4; i++){
            int nextY = curY + moveY[i];;
            int nextX = curX + moveX[i];

            if(IsOut(nextY, nextX)) continue;
            if(visit[nextY][nextX][curK]) continue;

            q.push({{curK, curCount+1}, {nextY, nextX}});
            visit[nextY][nextX][curK] = true;  
        }
    }

    return false;
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> k;
    cin >> w >> h;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> map[i][j];
        }
    }

    if(!SearchCount())
        cout << -1 << '\n';
}

---

 NC 코테에서 쉬워보이는 BFS를 풀지 못했다는 아쉬움에 풀게 된 BFS 문제입니다. 기존의 4방향으로 이동하던 단순 BFS 와는 달리 8방향이 추가되어 총 12개 방향으로 갈 수 있게 된 문제입니다. 대신 추가된 8개 방향은 K번만 이동할 수 있어 이에 대한 제약조건이 필요한 문제였습니다.

queue<pair<pair<int, int>, pair<int, int>>> q;

 일단 큐에 <현재 말처럼 이동한 횟수, 현재 이동 횟수>, <Y, X> 를 넣어주면서 계산을 했고

        // can horse movement
        if(curK < k){
            for(int i = 0; i < 8; i++){
                int nextY = curY + horseMove[i].first;
                int nextX = curX + horseMove[i].second;

                if(IsOut(nextY, nextX)) continue;
                if(visit[nextY][nextX][curK+1]) continue;

                q.push({{curK+1, curCount+1}, {nextY, nextX}});
                visit[nextY][nextX][curK+1] = true;
            }
        }

        // normal movement
        for(int i = 0; i < 4; i++){
            int nextY = curY + moveY[i];;
            int nextX = curX + moveX[i];

            if(IsOut(nextY, nextX)) continue;
            if(visit[nextY][nextX][curK]) continue;

            q.push({{curK, curCount+1}, {nextY, nextX}});
            visit[nextY][nextX][curK] = true;  
        }

 이후 K횟수가 남았는지를 체크하면서 남았다면 말의 움직임을 해보고 아니면 하지 않는 방식으로 했습니다. 이렇게 기존 BFS 에 K 추가만 넣으면 쉽게 풀이할 수 있는 문제였습니다.