[백준OJ] 1761번 정점들의 거리

www.acmicpc.net/problem/1761

1761번: 정점들의 거리

---

 

-풀이-

1. 입력받은 숫자와 거리로 graph를 만든다.

2. DFS를 이용하여 루트가 1인 트리의 깊이와 부모를 설정해준다.

3. LCA 알고리즘을 이용하여, 최소 공통조상까지 올라가며, 부모로 올라갈때 거리를 전부 더해준다.

 

-시간복잡도-

LCA알고리즘을 총 O(N)의 시간이 걸리게 구현하였다.  O(logN)으로 구현하면 더 빠를것이다.

 

-코드-

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 40001
using namespace std;

int n, m;
vector<pair<int,int>> maze[40001];
vector<pair<int, int>> op;
int depth[MAX];
int parent[MAX];

int get_value(int a, int p) {
	for (int i = 0; i < maze[a].size(); i++) {
		if (maze[a][i].first == p) {
			return maze[a][i].second;
		}
	}
}

int get_lca(int a, int b) {
	int result = 0;

	if (depth[a] > depth[b]) {
		while (depth[a] > depth[b]) {
			result += get_value(a, parent[a]);
			a = parent[a];
		}
	}
	else {
		while (depth[a] < depth[b]) {
			result += get_value(b, parent[b]);
			b = parent[b];
		}
	}

	while (a != b) {
		result += get_value(a, parent[a]);
		a = parent[a];
		result += get_value(b, parent[b]);
		b = parent[b];
	}
	return result;
}

void make_depth(int now, int p) {
	depth[now] = depth[p] + 1;
	parent[now] = p;

	int len = maze[now].size();
	for (int i = 0; i < len; i++) {
		int next = maze[now][i].first;
		if (next != p) {
			make_depth(next, now);
		}
	}
}

void input() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b, dist;
		cin >> a >> b >> dist;
		maze[a].push_back({ b,dist });
		maze[b].push_back({ a,dist });
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		op.push_back({ a,b });
	}
}

void solve() {
	depth[0] = -1;
	make_depth(1,0);

	for (int i = 0; i < m; i++) {
		int a = op[i].first;
		int b = op[i].second;

		cout << get_lca(a, b) << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	input();
	solve();
}