[16928] 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

<문제>

정점이 100개, 입력으로 들어오는 사다리와 뱀만 구현하면, 평범한 최단경로 bfs문제와 같아진다.

주사위를 던져서 나올 수 있는 경우는 항상 6개, 당연히 모든 경우를 각각 queue에 push해주어야 한다.

현재 정점이 cur, next={cur+1, cur+2 ... cur+6}으로 구성되어 있을것이다.

next에 뱀이나 사다리가 없다면 바로 next를 push한다.

뱀이 있다면, 뱀을 타고 떨어지게 되는 장소를 next 대신 push해주고, 사다리라면 올라갈 장소를 push한다.

 

특정 장소에 뱀이있든, 사다리가 있든, 아무것도 없든 특정 장소를 재방문할 이유가 없으므로

visited는 1차원으로, visited[101]처럼 선언해주면 충분하다.

 

애초에 큐에 들어갈 원소가 100개밖에 안되어서, 구현을 비효율적으로 해도 전혀 문제되지 않는다.

인접행렬로 O(100)씩 시간을 사용하며 push해도, 100*100 < 100'000'000 이므로 널널하다.

인접리스트처럼 구현하면, 뱀과 사다리에 중복이 없으므로 q.push(adj[next][0])처럼 구현할수도 있겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> up[101];
vector<int> down[101];
int main(void) {
    cin >> n >> m;
    int i, j;
    for (i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        up[a].push_back(b);
    }
    for (i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        down[a].push_back(b);
    }
    queue<pair<int, int>> q;
    q.push({1, 0});
    bool visited[101] = {0};
    visited[1] = true;
    while (!q.empty()) {
        int cur = q.front().first;
        int turn = q.front().second;
        q.pop();
        if (cur == 100) {
            cout << turn;
            break;
        }
        for (int next :
             {cur + 1, cur + 2, cur + 3, cur + 4, cur + 5, cur + 6}) {
            if (next > 100) break;
            if (visited[next] == true) continue;
            if (!up[next].empty()) {
                q.push({up[next][0], turn + 1});
                visited[up[next][0]] = true;
            } else if (!down[next].empty()) {
                q.push({down[next][0], turn + 1});
                visited[down[next][0]] = true;
            } else {
                q.push({next, turn + 1});
                visited[next] = true;
            }
        }
    }
    return 0;
}