백준 BOJ 5214 - 환승

간선을 생으로 구현하면 MLE가 나오는 문제

간선의 갯수를 줄이기 위해서는

더미노드를 만들어서

하이퍼 튜브가 문어발 같은 느낌으로 펼쳐지게 설계해주면 된다.

그러면 모든 노드를 최소한의 간선만 가지고( 정점을 하나 더 써서 )

이어줄 수 있고,

 

테스트케이스의 정답을 더미노드를 사용해서

문제를 해결하면

 

1 K 3 K 6 K 9 가 되는데,

정답, 즉 4를 N이라 하면

더미노드 K의 갯수는 N-1개 이다.

따라서 실제 정답은

우리가 bfs를 통해 구해준 가중치를 K로 두었을때

(K+1)/2를 출력해주면

답이 된다.

 

메모리 아끼는 팁으로는

가중치를 vis배열이랑 같이 묶어서

한번에 저장해줄 수 있다는 정도?

위의 더미노드를 만든다는 생각에만 도달하면 쉽게 AC를 받을 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

vector<int> edge[123456];
int vis[123456] = {0};
queue<int> q;

int main(){
	int n,k,m;
	int tmp;
	scanf("%d %d %d", &n, &k, &m);
	for(int i=n+1; i<m+n+1; i++){
		for(int j=0; j<k; j++){
			scanf("%d", &tmp);
			edge[i].push_back(tmp);
			edge[tmp].push_back(i);
		}
	}
	
	int node;
	q.push(1);
	vis[1] = 1;
	
	while(!q.empty()){
		node = q.front();
		q.pop();
		       
		for(int i=0; i<edge[node].size(); i++){
			if( vis[edge[node][i]] == 0 ){
				q.push(edge[node][i]);
				vis[edge[node][i]] = vis[node]+1;
			}
		}
	}
	if(vis[n] == 0) printf("-1");
	else printf("%d", (vis[n]+1)/2);
	return 0;
}