[BFS] 5214번 환승

5214번 환승

 

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

 

문제

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

 

입력

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

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

 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

 

예제 입력

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

 

예제 출력

4

 

해결방법

최단 거리를 찾는 BFS 탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

간단한 그래프 탐색 문제라고 생각했지만 메모리 초과가 발생했다 (흑흑)

 

처음 접근 방법은 각 하이퍼튜브의 정보를 입력받아 모든 간선을 연결하였다

for(int i=0; i<m; i++){
    // 하이퍼 튜브가 서로 연결하는 k개의 역의 정보 입력
    for(int j=0; j<k; j++){
        cin >> u;
        info.push_back(u);
    }
    // 간선을 연결
    for(int x=0; x<info.size(); x++){
        for(int y=0; y<info.size(); y++){
            if(x==y) continue;
            
            adj[info[x]].push_back(info[y]);
        }
    }
    info.clear();
}
// 간선의 중복을 삭제
for(int i=1; i<=n; i++){
    sort(adj[i].begin(),adj[i].end());
    adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
}

 

하지만 만약 하이퍼튜브가 1000개, 하이퍼튜브가 서로 연결하는 역의 개수가 1000개 라고 가정해보자

그렇다면 각 하이퍼튜브의 정보를 입력받고, 2중 for문을 사용하여 서로 간선을 연결해야한다

따라서 1000^3 의 시간으로 탐색이 불가능하다

다른 접근 방법이 필요했다....

 

 

⭐️ 새로운 솔루션 ⭐️

참고 블로그 : http://stack07142.tistory.com/135

 

흠.... 사실 내 머리로는 생각할 수 없는 솔루션이다....ㅋㅋ

사람들은 어떻게 이런 생각을 할까...

 

 

솔루션은 Dummy Station 을 만드는 것이다 !!

dummy station 을 임시 정거장이라고 생각을 하는게 좀 편할듯 싶다

그렇다면 총 역의 개수는 n + m 개이고 총 간선의 수는 k * m 개로 바뀌게 된다

 

기존의 경우는 m개의 하이퍼튜브에 대해 k개의 간선정보를 입력받아 서로 연결해야 했다

이때는 m개의 하이퍼 튜브에 대한 입력을 받는데 1000 의 시간이 들고 각각 입력에 대해 k개의 노드를 서로 연결해야하기 때문에 1000 * 1000 의 시간이 발생하여 총 1000^3 의 시간이 소요된다

 

하지만 dummy station 을 사용한다면 m개의 하이퍼튜브 입력에 대해 k개의 간선정보를 입력받아 dummy station에만 연결하기 때문에 1000 * 1000 의 시간만 발생한다

 

또한 dummy station 에 방문하는 경우는 이동 카운트를 증가시켜서는 안된다

따라서 다음노드가 1~n 일때만 카운트를 증가시켜준다

if(!visited[nxt]){
    int nxt_cnt = nxt > n ? cnt : cnt+1;
    q.push(node(nxt,nxt_cnt));
    visited[nxt] = true;
}

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 101001
#define INF 987654321
using namespace std;

/*
 
 n : 역의 개수
 k : 하이퍼튜브가 서로 연결하는 역의 개수
 m : 하이퍼튜브의 개수
 
 Dummy Station : 노드간의 간선을 하나의 dummy node로 관리하기 위함
 
 총 역의 개수는 n + m
 총 간선의 수는 k * m
 
*/

typedef pair<int, int> node;

int n,k,m,u;
bool visited[MAX];

vector<vector<int>> adj;

void bfs(){
    queue<node> q;
    q.push(node(1,1));
    visited[1] = true;
    
    while(!q.empty()){
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        if(now == n){
            cout << cnt << "\n";
            return;
        }
        
        for(int i=0; i<adj[now].size(); i++){
            int nxt = adj[now][i];
            
            if(!visited[nxt]){
                int nxt_cnt = nxt > n ? cnt : cnt+1;
                q.push(node(nxt,nxt_cnt));
                visited[nxt] = true;
            }
        }
    }
    
    cout << -1 << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> k >> m;
    
    adj.resize(n+1 + m);
    
    for(int i=1; i<=m; i++){
        for(int j=1; j<=k; j++){
            int u;
            cin >> u;
            
            adj[n+i].push_back(u);
            adj[u].push_back(n+i);
        }
    }
    
    memset(visited, false, sizeof(visited));
    
    bfs();
    
    return 0;
}