Baekjoon 1761 정점들의 거리

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

소스결과 6504 KB / 668 ms

언어 C++ 17

출처 Baekjoon

분류 LCA

 

설명

가중치가 있는 트리가 주어질 때 두 정점 사이의 가중치의 합을 출력한다.

 

기존 LCA문제에서 가중치가 추가된 LCA문제.

단지 루트 노드가 지정이 되지 않았기에 어느 노드를 기준으로 깊이를 설정해도 상관은 없다.

가장 일반적이게 1번 노드를 기준으로 깊이를 지정했다.

 

두 정점이 주어졌을 때 두 정점의 깊이를 맞추는 과정에서도 가중치의 합을 구해야 하는 것을 조심 해야한다.

두 정점의 깊이가 일치해 졌다면 같은 공통 조상까지 찾아가면서 가중치의 합을 구하면 최소 거리가 된다.

 

알고리즘

1. 간선과 가중치 정보를 입력 받는다.

2. 임의의 점( 소스코드에서는 1번)을 루트노드로 삼아 깊이와 부모 노드를 지정한다.

3. 거리를 구할 두 정점을 입력 받는다.

4. 두 정점의 깊이가 다를경우 깊이가 얕은 쪽으로 맞추며, 부모 노드로 이동하는 과정에서의 가중치의 합을 구한다.

5. 높이가 같아진 두 정점의 부모로 이동하면서 가중치의 합에 더한다.

6. 출력

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

struct Node {
	int vertex;
	int weight;

	Node() : vertex(0), weight(0) {};
	Node(int vertex, int weight) : vertex(vertex), weight(weight) {};
};

const int MAX = 40000;

vector<vector<Node>> node;
Node parent[MAX];
int level[MAX];
bool visitedCheck[MAX];

int balancing(int& vert1, int& vert2) {
	int res = 0;

	while (level[vert1] > level[vert2]) {
		res += parent[vert1].weight;
		vert1 = parent[vert1].vertex;
	}

	while (level[vert1] < level[vert2]) {
		res += parent[vert2].weight;
		vert2 = parent[vert2].vertex;
	}

	return res;
}

void setLevelNParent(int pos) {
	visitedCheck[pos] = true;
	int edgeCount = node[pos].size();

	for (int i = 0; i < edgeCount; i++){
		Node vert = node[pos][i];
		if (!visitedCheck[vert.vertex]) {
			parent[vert.vertex] = Node(pos, vert.weight);
			level[vert.vertex] = level[pos] + 1;

			setLevelNParent(vert.vertex);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n;

	node.resize(n);

	for (int i = 0; i < n - 1; i++) {
		int to, des, weight;
		cin >> to >> des >> weight;

		node[to - 1].push_back(Node(des -1, weight));
		node[des - 1].push_back(Node(to -1, weight));
	}

	setLevelNParent(0);

	cin >> m;

	for (int i = 0; i < m; i++) {
		int to, des;

		cin >> to >> des;

		to--; des--;

		int res = balancing(to, des);

		while (to != des) {
			res += parent[to].weight + parent[des].weight;

			to = parent[to].vertex;
			des = parent[des].vertex;
		}

		cout << res << '\n';
	}

	return 0;
}