[백준] No.5214 - 환승 (C++, BFS, 더미 노드)

문제

 

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

5214번: 환승

 

풀이

 

solved.ac 난이도: Gold 1

 

단순히 같은 하이퍼 튜브로 연결된 역들을 양방향 간선으로 이어 문제를 해결하면 시간 초과 또는 메모리 초과가 발생하는 문제였다.

 

그 이유는 최대 개수인 1000개의 역이 서로 연결된다면

양방향 간선으로 연결 시, 약 1,000,000(=1000^2) 개의 간선이 생성된다.

 

여기에 최대 1000개의 하이퍼 튜브가 존재한다면 

약 1,000,000,000(=1000^3)개의 간선이 존재하는 그래프가 생성된다.

이러한 단순한 그래프 생성은 시간 초과 또는 메모리 초과를 발생 시킨다.

 

따라서 같은 하이퍼 튜브로 연결되는 노드끼리는 더미 노드(Dummy node)라는 부모 노드로 연결을 시켜주자.

예를 들어 역 1, 2, 3을 연결하는 더미 부모 노드는 다음과 같다.

 

 

하이퍼 튜브로 연결된 K개의 역들을 이처럼 양방향 그래프로 표현하면

약 K*2 개의 간선이 생성된다.

여기에 하이퍼 튜브의 개수(M) 만큼을 곱해주면 M*K*2개의 간선으로 모든 그래프를 표현 가능하다.

K와  M이 1000으로 최댓값을 가지더라도 2,000,000개의 간선은 제한 메모리 내에서 구현이 가능하다.

 

이런 식으로 더미 노드를 각 하이퍼 튜브마다 한 개씩 생성하여 연결되는 역들과 이어 주자.

문제의 예제를 이러한 그래프로 표현하면 다음과 같다.

9 3 5

1 2 3

1 4 5

3 6 7

5 6 7

6 8 9

 

 

더미 노드 또한 한 개의 동일한 노드로 취급해주어야 하므로

각 역의 인접 간선을 저장하는 vector<vector<int>> adj의 크기를

station_num + 1 + hyper_tube_num 로 선언하여

역들의 정보 이후의 station_num + 1 위치부터는 더미 노드 나타내자.

 

 

  adj = vector<vector<int>>(station_num + 1 + hyper_tube_num);
 
  int station;
  for(int hyper_node_idx=station_num+1; hyper_node_idx<= station_num + hyper_tube_num ; ++hyper_node_idx){
 
    for(int i=0; i<linked_num ; ++i){
      cin>>station;
      adj[hyper_node_idx].push_back(station);
      adj[station].push_back(hyper_node_idx);
    }
  }

 

이제 모든 그래프를 생성했으므로 1번부터 시작하는 BFS를 통해 

N번 역까지 노드를 몇 번 지나는지 DP로 계산해주자.

 

 

코드