[백준 16928] 뱀과 사다리 게임

🔗알고리즘 문제

최근 그래프 탐색 문제에 재미 들린 것 같다. 이번에도 그래프 탐색 문제!! BFS를 조금 응용한 문제로 쉽게 해결할 수 있었다.

문제 분석

이 문제는 1부터 100번째 칸까지 있는 보드판에서 100번째칸에 도달 할 때 주사위를 던지는 최소 횟수를 구하는 문제이다.

이 때 보드에는 뱀과 사다리가 존재한다. 사다리와 뱀 모두 현재 위치에서 도착 위치로 이동할 수 있으며, 보드의 한 칸에 두개가 동시에 존재할 수 없다.

발상 & 알고리즘 설계

주사위를 던졌을 때는 1부터 6까지 총 6개의 값이 나오게 된다. 주사위를 던졌을 때 뒤로 가는 경우는 없다.

그러므로 주사위를 던졌을 때 나오는 칸은 1부터 6까지 for문을 진행했을 때 현재 칸 + i가 된다. 해당 칸에 사다리 또는 뱀이 존재한다면 사다리와 뱀의 끝 위치로 옮겨주었다.

이렇게 해서 나온 next값이 아직 탐색하지 않은 곳이고 100보다 작다면 next위치에 현재까지 주사위를 굴린 횟수를 저장하여 준다.

모든 탐색이 끝난 후 100번째 칸에 저장되어 있는 값을 출력하면 주사위를 몇번 굴려야 100번칸에 도착하는지 알 수 있다.

코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

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

    vector<int> v[101] = {};
    int check[101] = {};

    int n;
    int m;

    cin >> n >> m;

    for(int i = 0; i < n + m; i++){
        int start;
        int end;
        cin >> start >> end;
        v[start].push_back(end);
    }

    queue<int> q;
    q.push(1);

    while(q.empty() == false){
        int node = q.front();
        q.pop();

        for(int i = 1; i <= 6; i++){
            int next = node + i;

            if(next > 100)
                break;

            if(v[next].empty() == false){
                next = v[next].back();
            }

            if(check[next] > 0)
                continue;

            check[next] = check[node] + 1;
            q.push(next);
        }
    }

    cout << check[100];
}