백준 5214번 환승 - C++ 풀이

---

 

1. 하이퍼 튜브도 노드로 생각한다.
2. 일반 노드 -> 하이퍼 튜브 노드로 가는 간선의 가중치는 0으로 처리한다.
3. BFS를 이용해 1번 정점과 N번 정점 사이의 거리를 구한다.

 

1. 하이퍼튜브도 노드로 생각한다.

 하나의 하이퍼튜브로 연결된 K개의 노드들을 전부 간선으로 이어주려면 O(KM^2)의 시간 복잡도와 공간 복잡도가 필요하다. K, M이 최대 1,000이므로 이 방법은 사용할 수 없다.

 대신 하이퍼 튜브를 가상의 노드로 생각하는 방법을 사용한다. 하이퍼 튜브 H로 노드 1, 2, 3이 연결되어있다면 1, 2, 3번 노드 사이에 간선을 추가하지 않고 H번 노드와 각각 1, 2, 3번 노드로 가는 간선 3개 H-1, H-2, H-3만 추가해준다. 결과적으로 1, 2, 3번 노드 사이에 이동이 가능하되 간선의 개수는 K개로 줄어들었다.

 

2. 일반 노드 -> 하이퍼튜브 노드로 가는 간선의 가중치는 0으로 처리한다.

 그런데 이렇게 되면 하이퍼튜브로 연결되어있는 두 노드 사이의 거리가 2가 되게 된다. 출발 노드에서 하이퍼 튜브 노드로 가는 거리 1, 다시 하이퍼 튜브 노드에서 도착 노드로 가는 거리 1이 되기 때문이다. 하이퍼 튜브 노드는 가상의 노드이므로 일반 노드에서 하이퍼 튜브 노드 방향으로 가는 간선의 가중치는 0으로 처리해준다.

 

3. BFS를 이용해 1번 정점과 N번 정점 사이의 거리를 구한다.

 이제 BFS를 이용해서 1번 정점과 N번 정점 사이의 최단 거리를 구한다.

반응형

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

int N, K, M;
vector<int> adjs[101001];

int BFS(int from, int to) {
    queue<pii> q;
    vector<bool> visit(101001, 0);
    
    q.push({1, from});
    visit[from] = true;
    
    while (!q.empty()) {
        int dist = q.front().first;
        int curr = q.front().second;
        q.pop();
        
        if (curr == to) return dist;
        
        for (auto next: adjs[curr]) {
            int nDist = (next > N) ? dist : dist + 1;
            
            if (!visit[next]) {
                q.push({nDist, next});
                visit[next] = true;
            }
        }
    }
    
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> K >> M;
    for (int i=1; i<=M; i++) {
        for (int j=0; j<K; j++) {
            int temp; cin >> temp;
            // 하이퍼튜브도 노드로 처리한다
            // N+i번 노드 = i번 하이퍼튜브
            adjs[temp].push_back(N+i);
            adjs[N+i].push_back(temp);
        }
    }
    
    cout << BFS(1, N);

    return 0;
}