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

📌문제 링크

---

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

📌문제 설명

---

사다리와 뱀을 각각 “특정 위치에서 다른 위치로의 순간 이동”으로 간주하며, 각 칸까지의 최소 이동 횟수를 계산하기 위해 배열 mp를 사용합니다. BFS는 현재 위치에서 주사위를 굴려 나올 수 있는 최대 6개의 다음 칸을 탐색하며, 도착한 칸이 사다리나 뱀의 시작점이라면 해당 이동을 적용해 새로운 칸으로 이동합니다. 이 과정에서 이미 방문했거나 더 효율적으로 도달할 수 있는 경우만 큐에 추가하여 불필요한 계산을 줄입니다. 이는 그래프에서 간선 비용이 일정한 경우 BFS로 최단 경로를 구할 수 있다는 직관에서 출발했습니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <climits>
#include <queue>
using namespace std;
unordered_map<int, int> ladderMap;
unordered_map<int, int> snakeMap;
int N, M, mp[101];

void input(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        int x, y;
        cin >> x >> y;
        ladderMap.insert({x, y});
    }
    for(int i = 0; i < M; i++){
        int u, v;
        cin >> u >> v;
        snakeMap.insert({u, v});
    }
}

void bfs(){
    for(int i = 1; i <= 100; i++){
        mp[i] = INT_MAX;
    }
    queue<pair<int, int>> q;
    q.push({1, 0});
    mp[1] = 0;
    while(!q.empty()){
        auto [idx, cnt] = q.front();
        q.pop();
        if(idx == 100){
            continue;
        }
        for(int i = 1; i <= 6; i++){
            int next = idx + i;
            if(next > 100){
                continue;
            }
            if(ladderMap.find(next) != ladderMap.end()){
                if(mp[ladderMap[next]] > cnt + 1){
                    mp[ladderMap[next]] = cnt + 1;
                    q.push({ladderMap[next], cnt + 1});
                }
            }
            else if(snakeMap.find(next) != snakeMap.end()){
                if(mp[snakeMap[next]] > cnt + 1){
                    mp[snakeMap[next]] = cnt + 1;
                    q.push({snakeMap[next], cnt + 1});
                }
            }
            else if(mp[next] > cnt + 1){
                mp[next] = cnt + 1;
                q.push({next, cnt + 1});
            }
        }
    }
    cout << mp[100];
}

void solve(){
    input();
    bfs();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}