[백준 5214] 환승

문제

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

 

알고리즘

BFS

 

풀이

역들을 잇는 하이퍼튜브들이 주어질 때, $N$역으로 가기 위해 거쳐야하는 최소 역의 수를 구하는 문제입니다.

 

하이퍼튜브마다 일일이 역들을 연결하게 되면 메모리초과가 발생합니다. 대신에 하이퍼튜브마다 임의의 정점을 하나씩 만든 후, 각 역과 새로 만든 임의의 정점끼리 연결하여 메모리를 절약하였습니다. 

 

 

위 그림은 문제에서 주어진 첫번째 예시에서 첫번째 하이퍼튜브와 두번째 하이퍼튜브를 시각화한 것입니다. 저는 튜브마다의 임의의 정점을 100005+$i$로 하였습니다. 검은 실선을 가중치 1로 설정하여 풀고난 후, 마지막에 반을 나누어 실제로 거친 역의 수를 구했습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

typedef pair<int, int> pii;

int N, K, M;
vector<int> connected[105000];
vector<pii> adj[105000];
int visited[105000];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> K >> M;
    rep(i, M) {
        rep(j, K) {
            int x;
            cin >> x;
            connected[i].emplace_back(x);
        }

        rep(j, connected[i].size()) {
            int u = connected[i][j];
            int v = 100000 + i + 5;
            adj[u].emplace_back(v, 1);
            adj[v].emplace_back(u, 1);
        }
    }
    memset(visited, -1, sizeof(visited));
    queue<int> q;
    q.emplace(1);
    visited[1] = 0;
    while (!q.empty()) {
        int here = q.front();
        q.pop();
        if (here == N) break;
        for (auto [there, cost] : adj[here]) {
            if (~visited[there]) continue;
            visited[there] = visited[here] + cost;
            q.emplace(there);
        }
    }

    cout << (visited[N] == -1 ? -1 : (visited[N] / 2 + 1));
    return 0;
}