c++/알고리즘

[c++] 백준 - 도로 네트워크(lca)

hojung 2023. 3. 3.

728x90

1. 문제

2. 입 출력

3. 예제

4. 문제 해설

이 문제는 lca를 이용한 문제였다. 문제 자체에서 가장 root노드가 무엇인지 주진 않았지만 1번 노드를 root로 삼아 (왜냐하면 1번 노드는 항상 나오기 때문이다.) 트리를 구성하고 그 후 효율적인 lca풀이를 이용하면 충분히 구할 수 있는 문제이다.

이 문제는 또한 lca를 구성하는 과정에서 구간의 최댓값과 최솟 값을 저장하며 가야하는 문제이다. 따라서 dp문제의 성향이 강하다고 할 수 있겠다.

우선 효율적인 lca 풀이를 위해 tree를 구성해준다. 나는 bfs를 통해 트리를 만들어주었다.

void makeTree() {
	depth[1] = 1;
	q.push({ 1 });
	while (q.size()) {
		int curr = q.front(); q.pop();
		for (auto next : AL[curr]) {
			if (!depth[next.first]) {
				depth[next.first] = depth[curr] + 1;
				parent[next.first][0] = curr;
				min_road[next.first][0] = next.second;
				max_road[next.first][0] = next.second;
				q.push(next.first);
			}
		}
	}
}

dp배열 즉 depth는 트리의 height를 의미하고 parent는 그 노드의 부모를 의미한다. 또한 효율적인 lca풀이와 마찬가지로

parent배열과 min_road배열 max_road배열 세 가지를 각각 이차원 배열로 선언했는데 이 때 모두 parent[first][second]의 경우 first노드의 2 ^ second 부모의 값 또는 min_road[first][second]의 경우는 first노드 부터 2 ^ second부모 까지 도로의 최솟값 max_road는 최댓값을 의미한다.

위와 같이 트리를 만들어주고 각각의 dp배열의 0번째를 채우고 나면 이제 dp배열의 초기값을 채웠다 할 수 있겠다. 이제 dp배열을 만들어준다.

void makeParent() {
	for (int k = 0; k < HEIGHT - 1; k++) {
		for (int x = 1; x <= N; x++) {
			if (parent[x][k] != 0) {
				parent[x][k + 1] = parent[parent[x][k]][k];
				max_road[x][k + 1] = max(max_road[x][k], max_road[parent[x][k]][k]);
				min_road[x][k + 1] = min(min_road[x][k], min_road[parent[x][k]][k]);
			}
		}
	}
}

parent[x][k] = parent[parent[x][k-1]][k-1] 의 점화식을 따른다. 이는 parent 2^k = 2 ^ (k-1) + 2 ^ (k-1)의 점화식 성질을 따른 것이다.

void lca2(int l, int r) {
	if (depth[l] < depth[r]) swap(l, r);
	int diff = depth[l] - depth[r];
	int cnt = 0;
	int mn = INF, mx = 0;
	while (diff) {
		if (1 & diff) {
			mn = min(min_road[l][cnt], mn);
			mx = max(max_road[l][cnt], mx);
			l = parent[l][cnt];
		}
		cnt++;
		diff >>= 1;
	} // 둘의 depth를 맞춘다.
	//printf("afterl  : %d after r : %d\n", l, r);
	if (l != r) {
		for (int i = HEIGHT - 1; i >= 0; i--) {
			if (parent[l][i] != parent[r][i]) {
				mn = min(min_road[l][i], mn);
				mn = min(min_road[r][i], mn);
				mx = max(max_road[l][i], mx);
				mx = max(max_road[r][i], mx);
				l = parent[l][i];
				r = parent[r][i];
			}
		}
		if (min_road[l][0] != 0 && min_road[r][0] != 0) {
			mn = min(min_road[l][0], mn);
			mn = min(min_road[r][0], mn);
		}
		if (max_road[l][0] != 0 && max_road[r][0] != 0) {
			mx = max(max_road[l][0], mx);
			mx = max(max_road[r][0], mx);
		}
	}
	printf("%d %d\n", mn, mx);
}

위의 세 dp배열을 채워줬으면 이제 lca로직을 수행해야한다. 우선 둘의 높이를 맞춘 후 맨 위의 조상부터 차례대로 검사하여 다르다면 그 위치로 이동해가는 방식을 택한다. 위의 로직의 자세한 설명은 lca2문제를 풀며 설명해두었다.

위의 로직을 모두 통과하면 정답은 그 l과 r의 부모가 되므로 root가 아니라면 한 번더 수행해주어야한다.

5. 코드

/*
	sparse table을 유도한다. (K와 N이 크기 때문이다.)
*/
#pragma warning (disable : 4996)

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define  MAX 100000
#define INF 0x3f3f3f3f
#define HEIGHT 21
using namespace std;
int N, K;
vector<pair<int, int>>AL[MAX + 2];
int parent[MAX][HEIGHT];
int depth[MAX];
int min_road[MAX][HEIGHT];
int max_road[MAX][HEIGHT];
queue<int> q;
void makeTree() {
	depth[1] = 1;
	q.push({ 1 });
	while (q.size()) {
		int curr = q.front(); q.pop();
		for (auto next : AL[curr]) {
			if (!depth[next.first]) {
				depth[next.first] = depth[curr] + 1;
				parent[next.first][0] = curr;
				min_road[next.first][0] = next.second;
				max_road[next.first][0] = next.second;
				q.push(next.first);
			}
		}
	}
}

void makeParent() {
	for (int k = 0; k < HEIGHT - 1; k++) {
		for (int x = 1; x <= N; x++) {
			if (parent[x][k] != 0) {
				parent[x][k + 1] = parent[parent[x][k]][k];
				max_road[x][k + 1] = max(max_road[x][k], max_road[parent[x][k]][k]);
				min_road[x][k + 1] = min(min_road[x][k], min_road[parent[x][k]][k]);
			}
		}
	}
}

void lca2(int l, int r) {
	if (depth[l] < depth[r]) swap(l, r);
	int diff = depth[l] - depth[r];
	int cnt = 0;
	int mn = INF, mx = 0;
	while (diff) {
		if (1 & diff) {
			mn = min(min_road[l][cnt], mn);
			mx = max(max_road[l][cnt], mx);
			l = parent[l][cnt];
		}
		cnt++;
		diff >>= 1;
	} // 둘의 depth를 맞춘다.
	//printf("afterl  : %d after r : %d\n", l, r);
	if (l != r) {
		for (int i = HEIGHT - 1; i >= 0; i--) {
			if (parent[l][i] != parent[r][i]) {
				mn = min(min_road[l][i], mn);
				mn = min(min_road[r][i], mn);
				mx = max(max_road[l][i], mx);
				mx = max(max_road[r][i], mx);
				l = parent[l][i];
				r = parent[r][i];
			}
		}
		if (min_road[l][0] != 0 && min_road[r][0] != 0) {
			mn = min(min_road[l][0], mn);
			mn = min(min_road[r][0], mn);
		}
		if (max_road[l][0] != 0 && max_road[r][0] != 0) {
			mx = max(max_road[l][0], mx);
			mx = max(max_road[r][0], mx);
		}
	}
	printf("%d %d\n", mn, mx);
}

void input() {
	scanf("%d", &N);
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		AL[a].push_back({ b,c });
		AL[b].push_back({ a,c }); // 인접리스트
	}

	scanf("%d", &K);
}
int main() {

	input();
	makeTree();
	makeParent();
	for (int i = 0; i < K; i++) {
		int d, e;
		scanf("%d %d", &d, &e);
		lca2(d, e);
	}

	return 0;
}

첫 번째는 그냥 lca풀이로 풀다가 시간초과가 나버렸다.