BOJ 1761 - 정점들의 거리

문제 링크(Link)

---

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

문제 해결 (Solution)

---

 1. 문제에서 주어지는 그래프가 트리(Tree)임을 알고있다.

 2. 트리에서 두 정점의 거리를 일반적인 방법으로 구하기 위해선 시간복잡도 O(N)이 소요된다. 쿼리의 개수를 고려하면 전체 시간복잡도는 O(NM)이 소요된다. 즉, 400,000,000(4억) 이므로 시간 초과에서 자유로울 수 없다.

 3. dp를 이용한 LCA(최소 공통 조상) 알고리즘을 이용하면 O(logN)만에 두 정점의 거리를 구할 수 있다.(트리에서만...) 

 4. dp[i][j] = 정점 i에서의 2^j 번째 조상.

 5. dist (dist[i] = 루트에서 부터 정점 i 까지의 거리) 라는 배열을 활용해서 두 정점사이의 거리를 구할 수 있다.

 6. 두 정점 i, j 사이의 거리 = dist[i] + dist[j] - 2*dist[LCA(i,j)]

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 -

참고(Reference)

---

 - 아이디어를 받은 Blog : http://jason9319.tistory.com/110

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<iostream>
	#include<cstdio>
	#include<string>
	#include<cstring>
	#include<algorithm>
	#include<queue>
	#include<set>
	#include<ctime>
	#include<vector>
	using namespace std;
	int N,M;
	vector<pair<int,int> > graph[40003];
	int parent[40003][20];
	int depth[40003],dist[40004];
	void makeTree(int here){
	for(int i=0;i<graph[here].size();i++){
	int there = graph[here][i].first;
	int cost = graph[here][i].second;
	if(depth[there]==-1){
	depth[there]=depth[here]+1;
	dist[there]=dist[here]+cost;
	parent[there][0]=here;
	makeTree(there);
	}
	}
	}
	int main(){
	memset(parent,-1,sizeof(parent));
	memset(depth,-1,sizeof(depth));
	cin >> N;
	for(int i=0;i<N-1;i++){
	int u,v,w;
	scanf("%d %d %d",&u,&v,&w);
	graph[u].push_back({v,w});
	graph[v].push_back({u,w});
	}
	depth[1]=0,dist[1]=0;
	makeTree(1);
	for(int j=0;j<18;j++){
	for(int i=1;i<=N;i++){
	if(parent[i][j]!=-1)
	parent[i][j+1]=parent[parent[i][j]][j];
	}
	}
	cin >> M;
	for(int i=0;i<M;i++){
	int ans=0;
	int u,v;
	scanf("%d %d",&u,&v);
	ans+=(dist[u]+dist[v]);
	if(depth[u]<depth[v])
	swap(u,v);
	int diff = depth[u]-depth[v];
	for(int j=0;diff;j++){
	if(diff%2==1){
	u=parent[u][j];
	}
	diff/=2;
	}
	if(u!=v){
	int idx=0;
	for(int j=18;j>=0;j--){
	if(parent[u][j]!=-1&&parent[u][j]!=parent[v][j]){
	u=parent[u][j];
	v=parent[v][j];
	}
	}
	u=parent[u][0];
	}
	ans-=(2*dist[u]);
	printf("%d\n",ans);
	}
	return 0;
	}

view raw BOJ 1761.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.