[P4] 백준 3176번 도로 네트워크 C++ LCA, 트리, 최소 공통 조상

리뷰

 

두 노드에서 출발해 LCA에 달할때 까지 도로 중 가장 짧은 거리와 가장 긴 거리를 구하는 문제

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

 

문제 풀이

1. 도시의 최대 개수는 10만이므로 MAX_N을 10만 1로, LOG를 MAX_N을 LOG2를 취한 값 보다 크게 20으로 설정한다.
2. 도시의 개수 n과 쿼리의 개수 k를 전역 변수로 설정한다.
3. 부모 도시를 담을 배열par, 짧은 거리 및 긴 거리를 저장할 배열 mn, mx을 MAX_N * LOG 크기로 설정한다.
4. 깊이를 담을 배열dep, 유니온 파인드용 배열 nodes를 MAX_N크기로 설저어한다.
5. 인접 리스트 정보를 담을 구조체 Link를 만들어 주고 Link타입 벡터 links를 MAX_N크기로 설정한다.
6. n값을 입력 받고 1~n 도시를 각각 자기 자신을 value로 받도록 nodes 배열을 초기화 해준다.
7. n - 1개의 간선을 정보를 입력 받고 links 벡터에 양방향으로 추가해 주고, a와 b를 유니온 처리 해준다.
8. 자기 자신을 value로 갖는 도시를 찾아 해당 도시를 root로 설정해 준다.
9. dfs를 통해 기초 세팅을 진행해 준다, root부터 시작하여 parent는 -1, 깊이와 도로의 길이는 0으로 시작한다.
10. 자기 자신의 2^0번째 부모를 parent로 세팅해주고 mn, mx역시 2^0번째 부모의 도로 길이를 모두 c로 세팅해 준다. 자신의 dep은 depth를 넣어주면 된다.
11. 이후 자신에 연결된 인접리스트를 참조하며 재귀를 진행해 주면 된다. 기존의 node 위치는 child가 될 것이고 parent 위치는 자기자신인 node가 된다, depth는 기존보다 1증가, c는 자신의 도로 길이인 w가 된다.
12. preprocess 함수를 통해 2^i번째 부모와 mn, mx값을 갱신해 준다.
13. k번의 쿼리를 수행한다, 도로 정보를 찾을 a, b를 입력 받고 lca 함수의 인자로 전달해 준다.
14. lca함수를 통해 최소 공통 부모를 찾고, 해당 부모까지의 가장 짧은 도로와 긴 도로를 찾아줄 것이다.
15. min_val은 100만보다 큰 값으로, max_val은 1보다 작은 값으로 초깃값을 설정해 준다.
16. 비교를 쉽게 하기 위해 만약 u보다 v의 깊이가 더 크다면 둘을 교체해 준다.
17. u와 v의 깊이를 맞춰주어야 한다, 둘의 깊이 차이를 diff에 받아온다.
18. 이후 diff가 0이 될때까지 깊이를 맞춰주는 작업을 하고, 해당 부분에서 min_val과 max_val도 갱신해 준다.
19. 깊이를 맞춰주고 나서 u와 v가 같다면 바로 min_val과 max_val을 리턴해 주면 된다.
20. 그게 아니라면 u와 v의 깊이를 2^i번씩 올려주며 LCA의 바로 전까지 이동하는 작업을 수행해 준다.
21. 마찬가지로 해당 작업을 하면서 mn, mx값을 계속 갱신해 주어야 한다.
22. 모든 작업이 마무리 되었을 때 u와 v의 바로 위 조상이 LCA가 된다, 해당 도시까지의 거리까지 mn, mx를 갱신해 주고 최종적으로 min_val과 max_val을 리턴해 준다.
23. min_val을 출력하고 한칸 띄워준 다음 max_val을 출력, 이후 줄바꿈을 해주면 된다.

 

참고 사항

u와 v의 깊이를 맞춰줄땐 단방향에서 올라오는 경우이기 때문에 min_val, max_val을 u 기준으로만 비교하여 갱신해 주면 된다.

이후 높이를 맞추는 작업에선 양방행에서 올라오는 경우이기 때문에 u, v모두 비교하여 갱신해 주어야 한다.

min_val, max_val에 적용되는 모든 갱신 작업은 u와 v가 갱신되기 전에 진행해 주어야 한다.

lca 함수를 void로 설정하고 바로 값을 출력해 주어도 된다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX_N = 100001;
const int LOG = 20;

int n, k;
int par[MAX_N][LOG];
int mn[MAX_N][LOG];
int mx[MAX_N][LOG];
int dep[MAX_N];
int nodes[MAX_N];

struct Link {
	int e, w;
};
vector<Link> links[MAX_N];

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A == B) return;
	nodes[B] = A;
}

void dfs(int node, int parent, int depth, int c) {
	par[node][0] = parent;
	mn[node][0] = c;
	mx[node][0] = c;
	dep[node] = depth;
	for (Link link : links[node]) {
		int child = link.e, w = link.w;
		if (parent != child) dfs(child, node, depth + 1, w);
	}
}

void preprocess() {
	for (int i = 1; i < LOG; i++) {
		for (int j = 1; j <= n; j++) {
			if (par[j][i - 1] != -1) {
				par[j][i] = par[par[j][i - 1]][i - 1];
				mn[j][i] = min(mn[par[j][i - 1]][i - 1], mn[j][i - 1]);
				mx[j][i] = max(mx[par[j][i - 1]][i - 1], mx[j][i - 1]);
			}
		}
	}
}

pair<int, int> lca(int u, int v) {
	int min_val = 2e9, max_val = -1;
	if (dep[u] < dep[v]) swap(u, v);
	
	int diff = dep[u] - dep[v];
	for (int i = 0; i < LOG; i++) {
		if ((diff >> i) & 1) {
			min_val = min(min_val, mn[u][i]);
			max_val = max(max_val, mx[u][i]);
			u = par[u][i];
		}
	}

	if (u == v) return { min_val, max_val };

	for (int i = LOG - 1; i >= 0; i--) {
		if (par[u][i] != par[v][i]) {
			min_val = min({ min_val, mn[u][i], mn[v][i] });
			max_val = max({ max_val, mx[u][i], mx[v][i] });
			u = par[u][i];
			v = par[v][i];
		}
	}

	min_val = min({ min_val, mn[u][0], mn[v][0] });
	max_val = max({ max_val, mx[u][0], mx[v][0] });

	return { min_val, max_val };
}

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

	cin >> n;
	for (int i = 1; i <= n; i++) nodes[i] = i;

	for (int i = 1; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		links[a].push_back({ b, c });
		links[b].push_back({ a, c });
		Union(a, b);
	}

	int root = 1;
	for (int i = 1; i <= n; i++) if (nodes[i] == i) {
		root = i; break;
	}

	dfs(root, -1, 0, 0);
	preprocess();

	cin >> k;
	while (k--) {
		int a, b; cin >> a >> b;
		pair<int, int> ans = lca(a, b);
		cout << ans.first << " " << ans.second << "\n";
	}
}