백준 5214 환승

 

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

---

처음에 그냥 모든 가중치가 1인 경로에서 최단거리를 찾는 문제라 생각하여 bfs로 정점과 간선의 정보를 사용해 풀이하였는데,, 메모리 초과가 나와서 마음이 힘들었다..

이 문제를 해결하기 위해서는, 정점 사이 연결을 확인하여 계산하는 과정에서 메모리 초과가 일어나기 때문에, 간선 정보보다 하이퍼튜브 개념을 활용하여 풀이해야한다. 

 

개별 노드와 하이퍼 튜브의 방문 여부를 체크하여 재방문이 일어나지 않도록 한다. 

1번 노드부터 확인하며 인접 노드를 확인하는데, 이때 인접 노드를 확인하는 방법은 

[현재 노드에 연결된 하이퍼 튜브]를 찾고 -> [그 하이퍼튜브에 연결된 노드를 탐색]하는 방식으로 진행하였다. 

 

1. 처음 큐에 1을 넣고, 1번 노드와 연결된 하이퍼튜브들을 방문한다. 
2. 이 하이퍼튜브들로 반복문을 돌면서 튜브 속 노드들을 확인한다.
3. 탐색한 노드 중 방문하지 않은 노드가 있다면 거리 정보를 갱신해주고 큐에 탐색한 노드를 삽입한다.
4. 큐에 원소가 없을 때까지 2, 3과정을 반복한다. 

 

 

d배열에 거리 정보를 저장했는데, ((현재 노드)와 연결된 하이퍼튜브)에 포함된 노드의 거리= 현재 노드의 거리 +1 로 계산했다.

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, k, m;
vector<vector<int>> node;  // 노드 -> 하이퍼튜브
vector<vector<int>> hyper; // 하이퍼튜브 -> 노드
vector<int> d;             // 각 노드까지의 최소 거리

void bfs() {
    queue<int> q;
    vector<bool> visit_hyper(m + 1, false); // 하이퍼튜브 방문 체크
    vector<bool> visit_node(n + 1, false); // 노드 방문 체크

    q.push(1);           // 노드 1 에서 시작
    visit_node[1] = true;
    d[1] = 1;            // 1번 노드는 거리 1

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        // 현재 역에 연결된 하이퍼튜브를 탐색
        for (int hyper_idx : node[cur]) {
            if (visit_hyper[hyper_idx]) continue; // 이미 방문한 하이퍼튜브는 스킵
            visit_hyper[hyper_idx] = true;

            // 하이퍼튜브에 연결된 역 탐색
            for (int next_node : hyper[hyper_idx]) {
                if (!visit_node[next_node]) { // 아직 방문하지 않은 노드
                    visit_node[next_node] = true;
                    d[next_node] = d[cur] + 1; // 거리 갱신
                    q.push(next_node);
                }
            }
        }
    }
}

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

    cin >> n >> k >> m;

    // 그래프 초기화
    node.resize(n + 1);    // 노드 -> 하이퍼튜브
    hyper.resize(m + 1);   // 하이퍼튜브 -> 노드
    d.resize(n + 1, 1e9); 

    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < k; j++) {
            int a;
            cin >> a;
            hyper[i].push_back(a);  // 하이퍼튜브에 연결된 노드 저장
            node[a].push_back(i);   // 노드에 연결된 하이퍼튜브 저장
        }
    }

    bfs(); 

    if (d[n] == 1e9) {
        cout << -1; // 도달 불가
    }
    else {
        cout << d[n]; // 최소 방문 역의 수
    }

    return 0;
}

 

계산을 하면서 내가 인덱스 정보를 맞게 주고 있는건가.. 땀흘리면서 풀었다.. 넘넘 어려웟어요