[백준] 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로 계산해주자.

 

 

코드

	#include<iostream>
	#include<queue>
	#include<string.h>
	#include<vector>
	using namespace std;
	int station_num, linked_num,hyper_tube_num ;
	vector<vector<int>> adj;
	int passed_station[101001];
	int HyperBFS(){
	queue<int> que;
	que.push(1);
	passed_station[1] = 1;
	int station_idx;
	while(!que.empty()){
	station_idx = que.front();
	que.pop();
	if(station_idx == station_num)
	return passed_station[station_idx];
	int next_station, next_cost = passed_station[station_idx]+1;
	for(int i=0; i< adj[station_idx].size() ; ++i){
	next_station = adj[station_idx][i];
	if(passed_station[next_station] == -1){
	que.push(next_station);
	passed_station[next_station] = next_cost;
	}
	}
	}
	return -1;
	}
	int main(){
	ios_base::sync_with_stdio(0);
	cin>>station_num>>linked_num>>hyper_tube_num;
	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);
	}
	}
	memset(passed_station, -1, sizeof(passed_station));
	int result = HyperBFS();
	if(result == -1)
	cout<<-1<<"\n";
	else
	cout<<(result+1)/2<<'\n';
	return 0;
	}

view raw [BaekJoon]_5214_환승.cpp hosted with ❤ by GitHub