백준 3176번 도로 네트워크

< 백준 3176번 도로 네트워크 - 마포 코딩박 >

사용한 알고리즘: LCA


 N개의 도시들과 각 도시를 연결하는 N-1개의 도로에 대한 정보가 입력됩니다. K개의 입력으로 주어지는 도시쌍 a,b 에 대해 a,b를 연결하는 도로들 중 최대, 최소 값을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 13~16)
 LCA 기본 구현에 쓰이는 'parent[i][k] : i의 2^k 번째 조상' 개념에 더불어 'Value[i][k] : i의 2^k 조상으로 갈 때 <최소길이, 최대길이>' 라는 pair 배열을 추가로 설정해줍니다.

(2) (코드 19~33)
 1번 도시를 root라 생각하고 depth[1]=1 라 하고 모든 노드의 depth를 설정해줍니다.
 이때 parent[i][0] 는 자신의 부모가 되고, Value[i][0] = <부모까지거리, 부모까지거리> 가 됩니다.

(3) (코드 47~59)
 기본적인 LCA 의 parent[i][k] 를 계산하는 과정에서 추가로 Value[i][k] 값도 함께 계산해 줍니다.

(4) (코드 60~97)
 K번 입력되는 도시 a,b 의 공통 조상을 찾아가며, 앞서 계산해 둔 Value[i][k] 값을 통해 a,b 사이 도로의 최소, 최대 값을 최신화 해줍니다.

	#include <iostream>
	#include <utility> // pair
	#include <algorithm>
	#include <vector>
	using namespace std;
	// town max
	const int TMAX = 1e5;
	// dist max ; 10^5 < 2^17
	const int DMAX = 17;
	typedef pair<int, int> pii;
	int N, K, Depth[TMAX+1];
	// parent[i][k] : i의 2^k 번째 조상번호
	int parent[TMAX+1][DMAX+1];
	// Value[i][k] : i의 2^k번째 조상까지의 pair< 작은길이, 큰길이 >
	pii Value[TMAX+1][DMAX+1];
	// < 연결된 도시 , 연결길이 >
	vector<pii> arr[TMAX+1];
	// 각 노드들의 depth 설정하는 함수
	void MakeTree(int curr){
	for(auto child: arr[curr]){
	int town = child.first;
	int BaseV = child.second;
	// 이미 돌아본 도시는 패스
	if(Depth[town]!=0) continue;
	Depth[town] = Depth[curr]+1;
	// 2^0 번째 부모 저장
	parent[town][0] = curr;
	// 바로 부모까지 작은길이 = 큰길이
	Value[town][0] = pii(BaseV,BaseV);
	MakeTree(town);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for(int i=0; i<N-1; ++i){
	int a, b, w;
	cin >> a >> b >> w;
	arr[a].push_back(pii(b,w));
	arr[b].push_back(pii(a,w));
	}
	// 1이 root 고 depth[1] = 1 로 설정
	Depth[1] = 1;
	// 각 노드 depth 설정
	MakeTree(1);
	// parent[i][k] 와 Value[i][k] 구하기
	for(int k=0; k<=DMAX; ++k){
	for(int i=2; i<=N; ++i){
	int Father = parent[i][k];
	if(Father){
	parent[i][k+1] = parent[Father][k];
	// 작은길이 업데이트
	Value[i][k+1].first = min(Value[i][k].first, Value[Father][k].first);
	// 큰길이 업데이트
	Value[i][k+1].second = max(Value[i][k].second, Value[Father][k].second);
	}
	}
	}
	cin >> K;
	for(int i=0; i<K; ++i){
	int a, b;
	cin >> a >> b;
	int mini = 1000000;
	int maxi = 0;
	if(Depth[a]<Depth[b]) swap(a,b);
	int Diff = Depth[a] - Depth[b];
	int cnt = 0;
	while(Diff){
	if(Diff%2==1){
	mini = min(mini, Value[a][cnt].first);
	maxi = max(maxi, Value[a][cnt].second);
	a = parent[a][cnt];
	}
	Diff/=2;
	cnt++;
	}
	if(a!=b){
	for(int k=DMAX; k>=0; k--){
	if(parent[a][k]!=parent[b][k]){
	mini = min(mini, Value[a][k].first);
	maxi = max(maxi, Value[a][k].second);
	a=parent[a][k];
	mini = min(mini, Value[b][k].first);
	maxi = max(maxi, Value[b][k].second);
	b=parent[b][k];
	}
	}
	mini = min(mini, Value[a][0].first);
	maxi = max(maxi, Value[a][0].second);
	mini = min(mini, Value[b][0].first);
	maxi = max(maxi, Value[b][0].second);
	a=parent[a][0];
	}
	cout << mini << ' ' << maxi << '\n';
	}
	return 0;
	}

view raw BOJ 3176.cpp hosted with ❤ by GitHub