BOJ 16928 - 뱀과 사다리 게임 / C++

문제 링크 : https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

 

풀이

입력 받을 때, 뱀과 사다리를 굳이 나누어 입력받을 필요 없이 하나의 지름길로 취급하여 n+m만큼 입력받는다.

지름길 변수 shortcut[a] = b의 의미는 a로 들어가면 b로 나오게 된다는 의미이다.

 

다음으로, BFS를 통해 시작점 1 카운트 0부터 시작하여 1~6의 주사위에 따른 탐색을 진행한다.

도중에 지름길을 만나면 지름길로 이동하는 방식으로 100이 되는 최소 경우의 수를 구하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, ans = 0;
int shortcut[101] = { 0, };
bool visited[101] = { false, };

int main(){
    cin >> n >> m;

    for(int i=0; i<n + m; i++){
        int a, b;
        cin >> a >> b;
        shortcut[a] = b;
    }

    queue<pair<int, int> > q;
    q.push(make_pair(1, 0));

    while(!q.empty()){
        int cur = q.front().first;
        int cnt = q.front().second;

        q.pop();
        visited[cur] = true;
        if(cur == 100) ans = cnt;

        for(int i=1; i<=6; i++){
            int next = cur + i;
            if(next > 100) continue;
            next = shortcut[next] == 0 ? next : shortcut[next];

            if(!visited[next]){
                visited[next] = true;
                q.push(make_pair(next, cnt + 1));
            }
        }
    }
    
    cout << ans;
}