백준 16928 - 뱀과 사다리 게임

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

 

다른 노드로 건너뛸 수 있는 간선이 주어진다는 것과 주사위의 점만큼 움직인다는 점을 기억하며 BFS를 수행하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int n, m;
unordered_map<int, int> warp;
bool visited[101];

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

    cin >> n >> m;

    for (int i = 0; i < n + m; ++i)
    {
        int go, to;
        cin >> go >> to;
        warp[go] = to;
    }

    queue<pii> q;
    q.push({1, 0});
    visited[1] = true;

    while (true)
    {
        auto cur = q.front();
        q.pop();
        
        for (int i = 1; i <= 6; ++i)
        {
            int nxt = i + cur.first;

            if (warp.count(nxt))
                nxt = warp[nxt];

            if (visited[nxt])
                continue;

            if (nxt >= 100)
            {
                cout << cur.second + 1;
                return 0;
            }

            visited[nxt] = true;
            q.push({nxt, cur.second + 1});
        }
    }
}