[Algorithm] 16928 뱀과 사다리 게임 - C++, BFS

16928번: 뱀과 사다리 게임

#include <iostream>
#include <queue>

using namespace std;

int ladder, snake;
int nextMap[200];
bool visit[101];

void MakeRoute(){
    int from, to;
    cin >> from >> to;
    nextMap[from] = to;
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i = 1; i <= 100; i++){
        nextMap[i] = i;
    }

    // input
    cin >> ladder >> snake;
    while(ladder--){
        MakeRoute();
    }
    while(snake--){
        MakeRoute();
    }
    
    // solution
    queue<pair<int, int>> dice;  // pos, count
    dice.push({1, 0});
    visit[1] = true;

    while (!dice.empty()){
        int curPos = dice.front().first;
        int count = dice.front().second;
        dice.pop();

        if(curPos == 100){
            cout << count << '\n';
            return 0;
        }

        for(int i = 1; i <= 6; i++){
            int nextPos = curPos+i;
            if(nextPos > 100)   continue;
            nextPos = nextMap[curPos+i];

            if(visit[nextPos])  continue;

            visit[nextPos] = true;
            dice.push({nextPos, count+1});
        }
    }
}

---

 nextMap 이란 배열을 선언해 이 배열을 '인덱스에 도달했을때 연결된 다음 지점'에 대한 정보로 사용했습니다. 사다리나 뱀이 없는 곳이라면 그냥 인덱스가 이 배열값이 되는 것이고 아닌 경우에는 견결된 곳으로 이동하게 만들어 주면 되는 것입니다.