[백준] 16928번 - 뱀과 사다리게임 c++

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

출처 : wikipedia

 

문제 설명

뱀과 사다리 게임을 들어본 사람들이 있을 거다. 

1부터 시작하여 100번 위치까지 도착하면 되는데 주사위를 굴렸을 때 도착한 위치에 사다리가 있다면 위로,

도착한 위치에 뱀이 있다면 아래로 내려가면 된다.

내가 주사위 수를 조작할 수 있다면 어떻게 최단 횟수로 100의 위치에 도착할 수 있을 것인가?

풀이 방법

BFS(너비우선탐색)으로 풀면 된다.

1번 칸부터 시작하여 주사위를 굴렸을 경우 1~6까지 전부 탐색해서 최솟값을 찾는다.

100번째 칸에 먼저 도착한 값이 최소경우가 된다.

 

예를 들어, 주어진 사다리와 뱀이 다음과 같다고 가정한다.

• 사다리:  2번 → 38번, 7번 → 14번, 8번 → 31번

• 뱀: 16번 → 6번, 49번 → 11번

 

그러면 게임 진행 과정은 아래와 같다.

시작 위치: 1번 칸

주사위 굴리기: 1~6

1+1 = 2 → 사다리 → 38번으로 이동

1+2 = 3

1+3 = 4

 …

 

2. 현재 위치: 38번

주사위 굴리기: 38+1 = 39, …, 38+6 = 44

 

3. 이렇게 BFS로 각 경우를 탐색하며 100번 칸에 도달할 때까지 반복한다.

 

 

풀이 코드

#include <iostream>
#include <queue>

using namespace std;

//100개의 노드
//1~6이 간선역할
int board[101];
bool visited[101];
queue<pair<int,int>> q;
int n,m;
int main() {
    cin >> n >> m;
    for(int i=1; i<101; i++) board[i] = i;
    for(int i=0; i<n+m; i++){
        int x, y;
        cin >> x >> y;
        board[x] = y;
    }
    
    q.push({1,0});
    visited[0] = true;
    
    while(!q.empty()){
        int current = q.front().first; //현재칸 처음은 1
        int rolls = q.front().second; //현재까지 굴린 주사위횟수 (처음은 0)
        q.pop();
        
        if(current == 100) { //100번째 위치에 왔으면
            cout << rolls << '\n'; //지금까지 굴린 주사위 수 출력
            return 0;
        }
        
        //주사위 굴리기
        for(int dice = 1; dice<=6; dice++){
            int next = current+dice;
            
            if(next > 100) continue;
            next = board[next];
            
            if(!visited[next]){
                visited[next] = true;
                q.push({next, rolls+1});
            }
        }
    }
    return 0;
}