[Algorithm] 16928: 뱀과 사다리 게임

• toc {:toc}

📦16928: 뱀과 사다리 게임

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-06
문제 확인하기

풀이

알고리즘 풀이를 검색해보면서 얍문님이 푸시는 틀처럼 나누어서 코드를 짜봤는데 명시적으로 나누니 빼뜨리지 않고 생각할 수 있어서 연습하기 좋은 것 같다. 당분간은 이렇게 유지해봐야겠다.

• 최솟값을 구하는 것이기 때문에 BFS로 풀이하고 가장 먼저 답이 나오면 중단하는 방식을 사용했다.
• 1~6까지의 숫자를 더하고 방문 체크, 방문하지 않았다면 이동해서 방문 처리를 한다. 이때 사다리, 뱀으로 연결되어 있다면 사다리, 뱀을 통해 이동한 후에 방문 체크하는 것이 아닌, 이동 전에 방문 체크를 한다.
• 주의할 점은 1~6 주사위를 반복해서 던질 때 중복되어 주사위나 이전 값이 더해지는 경우는 없는 지를 체크해야 한다.

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n';
using namespace std;
 
int snake[101];
int ladder[101];
int vis[101];
int n, m;
queue<pair<int, int>> q;
 
void Input(){
    cin >> n >> m;
 
    int val;
    for(int i=0; i<n; i++){
        cin >> val;
        cin >> ladder[val];
    }
    for(int i=0; i<m; i++){
        cin >> val;
        cin >> snake[val];
    }
}
 
int game(){
    int start = 1;
    vis[start] = 1;
    q.push({0, start});
 
    int prev_roll, prev;
    while(!q.empty()){
        auto info = q.front(); q.pop(); 
        prev_roll = info.first;
        prev = info.second;
        if(prev == 100) return prev_roll;
        for(int i=1; i<=6; i++){
            int cur = prev + i;
            int cur_roll = prev_roll + 1;
            if(vis[cur] == 1 || cur > 100 || cur < 1) continue;
            
            vis[cur] = 1;
            if(ladder[cur] != 0){
                cur = ladder[cur];
            }
            else if(snake[cur] != 0){
                cur = snake[cur];
            }
            q.push({cur_roll, cur});
        }
    }
}
 
void Solution(){
    cout << game() << endl;
}
 
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}