[C++][백준] 도로 네트워크(3176) - LCA

문제

N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다.

모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.

총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.

다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,000)

다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구해서 출력하면 된다.

 

출력

총 K개 줄에 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

 

풀이

LCA를 활용하여 문제를 풀이합니다. 기존 LCA에서는 parents 배열을 아래와 같이 정의했습니다.

parent[n][k] : n번 노드의 2^k 번째 위 조상 노드

 

마찬가지로 가장 짧은 도로의 길이, 가장 긴 도로의 길이도 dp 배열로 만들어줍니다.

minLength[n][k] : n번 노드에서 2^k번째 위 조상 노드까지 연결하는 경로 중 가장 짧은 도로 길이

maxLength[n][k] : n번 노드에서 2^k번째 위 조상 노드까지 연결하는 경로 중 가장 긴 도로 길이

 

// 전처리를 수행한다.
// 각 노드의 깊이, 부모를 계산한다.
void preprocessing1(int cur, int depth, int parent, int lengths) {
	visited[cur] = true;
	depths[cur] = depth;
	parents[cur][0] = parent; // parent는 cur노드의 바로 위 부모
	
	maxLength[cur][0] = lengths;
	minLength[cur][0] = lengths;

	for (int i = 0; i < myGraph[cur].size(); i++) {
		int next = myGraph[cur][i];
		int length = myCost[cur][i];

		if (visited[next] == false) {
			preprocessing1(next, depth + 1, cur, length);
		}
	}
}

먼저 LCA의 전처리 중 각 노드의 깊이, 부모를 계산하는 로직에서

부모까지의 경로를 maxLength[cur][0], minLength[cur][0]에 넣어줍니다.

 

 

// 조상 노드를 계산한다.
void preprocessing2() {
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i <= N; i++) {
			parents[i][j] = parents[parents[i][j - 1]][j - 1];
			maxLength[i][j] = max(maxLength[i][j - 1], maxLength[parents[i][j - 1]][j - 1]);
			minLength[i][j] = min(minLength[i][j - 1], minLength[parents[i][j - 1]][j - 1]);
		}
	}
}

LCA의 전처리 중 조상 노드를 계산하는 로직에서

maxLength, minLength 배열을 업데이트 해줍니다. 

 

예를 들어 maxLength[9][2]는 9번 노드의 2^2번째 부모까지 연결하는 경로 중 가장 긴 도로의 길이입니다.

 

이 값은 maxLength[9][1] vs maxLength[4][1] 이라고 할 수 있습니다.이때 4는 parents[9][1]입니다.

 

 

 

LCA 로직해서는 아래 로직을 추가합니다.

while (depths[first] != depths[second]) {
    for (int i = 20; i >= 0; i--) {
        if (depths[parents[first][i]] >= depths[second]) {
            maxAnswer = max(maxAnswer, max(maxAnswer, maxLength[first][i]));
            minAnswer = min(minAnswer, min(minAnswer, minLength[first][i]));
            first = parents[first][i];
        }
    }
}

두 노드의 깊이가 달라, 깊이를 맞춰주는 과정에서 maxAnswer, minAnswer를 갱신해줍니다. 

 

 

// 3. first 노드와 second 노드의 공통 조상이 다르다면 가능한 만큼 거슬러 올라간다.
	while (parents[first][0] != parents[second][0]) {
		for (int i = 20; i >= 0; i--) {
			if (parents[first][i] != parents[second][i]) {
				maxAnswer = max(maxAnswer, max(maxLength[first][i], maxLength[second][i]));
				minAnswer = min(minAnswer, min(minLength[first][i], minLength[second][i]));

				first = parents[first][i];
				second = parents[second][i];
			}
		}
	}

두 노드의 부모가 달라서 거슬러 올라가는 과정에서도 maxAnswer, minAnswer를 갱신해줍니다.

 

 

maxAnswer = max(maxAnswer, max(maxLength[first][0], maxLength[second][0]));
minAnswer = min(minAnswer, min(minLength[first][0], minLength[second][0]));

마지막으로 두 노드의 부모가 동일해졌을 때 maxAnswer, minAnswer를 갱신해줍니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 100010;
vector<int> myGraph[MAX];
vector<int> myCost[MAX];
int N, M;

int depths[MAX];
int parents[MAX][25];
bool visited[MAX] = { false, };

int maxLength[MAX][25]; // i번 노드에서 2^j번째 부모까지 모든 노드 중 최대길이(최댓값)
int minLength[MAX][25]; // i번 노드에서 2^j번째 부모까지 모든 노드 중 최소길이(최솟값)

int minAnswer = 987654321, maxAnswer = 0;

int max(int a, int b) {
	if (a > b) return a;
	else return b;
}

int min(int a, int b) {
	if (a < b) return a;
	else return b;
}

// 전처리를 수행한다.
// 각 노드의 깊이, 부모를 계산한다.
void preprocessing1(int cur, int depth, int parent, int lengths) {
	visited[cur] = true;
	depths[cur] = depth;
	parents[cur][0] = parent; // parent는 cur노드의 바로 위 부모
	
	maxLength[cur][0] = lengths;
	minLength[cur][0] = lengths;

	for (int i = 0; i < myGraph[cur].size(); i++) {
		int next = myGraph[cur][i];
		int length = myCost[cur][i];

		if (visited[next] == false) {
			preprocessing1(next, depth + 1, cur, length);
		}
	}
}

// 조상 노드를 계산한다.
void preprocessing2() {
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i <= N; i++) {
			parents[i][j] = parents[parents[i][j - 1]][j - 1];
			maxLength[i][j] = max(maxLength[i][j - 1], maxLength[parents[i][j - 1]][j - 1]);
			minLength[i][j] = min(minLength[i][j - 1], minLength[parents[i][j - 1]][j - 1]);
		}
	}
}

int LCA(int first, int second) {
	// 1. 두 노드의 깊이가 다르다면 깊이를 맞춰준다.
	if (depths[first] != depths[second]) {
		// 편의를 위해 first 노드의 깊이가 더 깊도록 설정한다. 
		if (depths[first] < depths[second]) {
			int tmp = second;
			second = first;
			first = tmp;
		}

		while (depths[first] != depths[second]) {
			for (int i = 20; i >= 0; i--) {
				if (depths[parents[first][i]] >= depths[second]) {
					maxAnswer = max(maxAnswer, maxLength[first][i]);
					minAnswer = min(minAnswer, minLength[first][i]);
					first = parents[first][i];
				}
			}
		}
	}

	// 2. 두 노드가 같다면 해당 노드가 최소 공통 조상 노드이다.
	if (first == second) return first;

	// 3. first 노드와 second 노드의 공통 조상이 다르다면 가능한 만큼 거슬러 올라간다.
	while (parents[first][0] != parents[second][0]) {
		for (int i = 20; i >= 0; i--) {
			if (parents[first][i] != parents[second][i]) {
				maxAnswer = max(maxAnswer, max(maxLength[first][i], maxLength[second][i]));
				minAnswer = min(minAnswer, min(minLength[first][i], minLength[second][i]));

				first = parents[first][i];
				second = parents[second][i];
			}
		}
	}

	maxAnswer = max(maxAnswer, max(maxLength[first][0], maxLength[second][0]));
	minAnswer = min(minAnswer, min(minLength[first][0], minLength[second][0]));
	return parents[first][0];
}

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

	for (int i = 0; i < N - 1; i++) {
		int first, second, money;
		scanf("%d %d %d", &first, &second, &money);

		myGraph[first].push_back(second);
		myGraph[second].push_back(first);

		myCost[first].push_back(money);
		myCost[second].push_back(money);
	}

	for (int p = 0; p < MAX; p++) {
		for (int q = 0; q < 25; q++) {
			minLength[p][q] = 987654321;
		}
	}

	preprocessing1(1, 0, 0, 0);
	preprocessing2();
	depths[0] = -1;

	scanf("%d", &M);

	for (int i = 0; i < M; i++) {
		minAnswer = 987654321, maxAnswer = 0;

		int first, second;
		scanf("%d %d", &first, &second);

		int lcaValue = LCA(first, second);

		printf("%d %d\n", minAnswer, maxAnswer);
	}

	return 0;
}