[BOJ] 백준 16928 - 뱀과 사다리 게임

문제 링크

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

풀이

단순 BFS문제입니다.

열심히 돌려서 답을 구해줍시다.

 

 

정답 코드

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

int n, m;
int up[111], down[111];
bool chk[111];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        up[x] = y;
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        down[x] = y;
    }
    chk[1] = true;
    queue<int> q;
    q.push(1);
    int ans = -1;
    while (!q.empty()) {
        int qsze = q.size();
        ans++;
        while (qsze--) {
            int now = q.front();
            q.pop();
            if (now == 100) {
                cout << ans;
                return 0;
            }
            for (int k = 1; k <= 6; k++) {
                int next = now + k;
                if (next > 100) continue;
                if (up[next] || down[next])
                    next = up[next] + down[next];

                if (chk[next]) continue;
                chk[next] = true;
                q.push(next);
            }
        }
    }
}