백준 1761번 정점들의 거리

< 백준 1761번 정점들의 거리 - 마포 코딩박 >

사용한 알고리즘: LCA


 트리에서 두 점 사이의 최단거리를 구하는 문제였습니다.
두 점의 공통 조상까지의 거리를 구하고 그 거리를 구해 문제를 해결했습니다.

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

(1) 두 노드와 입력되는 거리 a, b, cost 를 pair< 노드, 거리 > 형식으로 저장합니다.
양방향 이므로 a에 <b, cost> , b에 <a, cost> 를 각각 자식으로 저장했습니다.

(2) 1번 노드를 Root 으로 설정하고, 트리를 구현합니다.
( LCA 구현이 어려운 분들은 강산님의 블로그
https://blog.naver.com/kks227/220820773477 를 참고해주세요)

(3) 공통 조상으로 가는 LCA 를 구현하면서, 그 과정에서 지나는 노드와의 거리 ( 과정 (1)에서 저장한 < 노드, 거리> 에서 거리값 )을 더해줍니다.

LCA 를 사용하는 문제라고 쉽게 알 수 있었습니다. LCA 구현을 잘 하는게 중요한 문제였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 40001;
	// pair< 번호, 거리 >
	typedef pair<int, int> pii;
	int N, M, depth[MAX];
	pii parent[MAX][17];
	vector<pii> adj[MAX];
	void MakeTree(int curr){
	for (auto child: adj[curr]){
	if(depth[child.first]!=-1) continue;
	parent[child.first][0] = pii(curr,child.second);
	depth[child.first] = depth[curr]+1;
	MakeTree(child.first);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	memset(depth,-1,sizeof(depth));
	cin >> N;
	for (int i = 0; i < N-1; ++i){
	int a, b, cost;
	cin >> a >> b >> cost;
	adj[a].push_back(pii(b,cost));
	adj[b].push_back(pii(a,cost));
	}
	depth[1] = 0;
	MakeTree(1);
	for (int j = 0; j < 17; ++j){
	for (int i = 2; i <= N; ++i){
	int k = parent[i][j].first;
	if(k!=0) parent[i][j+1] = pii(parent[k][j].first, parent[k][j].second+parent[i][j].second);
	}
	}
	cin >> M;
	for (int i = 0; i < M; ++i){
	int a, b;
	int ans = 0;
	cin >> a >> b;
	// LCA 구현
	// a 의 depth 를 더 크게 생각하고싶다.
	if(depth[a] < depth[b]) swap(a,b);
	int diff = depth[a] - depth[b];
	int j = 0;
	while(diff){
	if(diff%2) {
	ans += parent[a][j].second;
	a = parent[a][j].first;
	}
	j++;
	diff/=2;
	}
	if(a!=b){
	// 2^16, ... 2, 1 번째 부모를 비교
	// 가장 중요한 스킬!!!!!!!!!!!1
	for (int j = 16; j>=0; j--){
	// 2^j번째 조상이 다른게 나오면 a, b 를 각각의 2^j번째 조상으로 위치변경
	if(parent[a][j].first!=parent[b][j].first){
	ans+=parent[a][j].second;
	ans+=parent[b][j].second;
	a = parent[a][j].first;
	b = parent[b][j].first;
	}
	}
	// 위 과정이 끝나면 최종 a, b 는 같은 부모 아래 있다.
	ans+=parent[b][0].second;
	ans+=parent[a][0].second;
	a = parent[a][0].first;
	}
	cout << ans << '\n';
	}
	return 0;
	}

view raw BOJ 1761.cpp hosted with ❤ by GitHub