BOJ3716 도로 네트워크

 

 

 

 

 

3716번 도로 네트워크

 

1부터 N까지의 도시를 연결하는 N-1개의 도로가 주어지고

서로 다른 두 도시 D, E가 주어지면 D와 E를 연결하는 도로 중

가장 짧은 것의 길이와 긴 것의 길이를 구한다.

 

이때 모든 서로 다른 두 도시간 경로는 한 개만 존재한다.

⇒ 주어진 그래프가 트리이다.

 

 

 

LCA문제임은 빠르게 파악할 수 있었다.

다만 공통조상뿐 아니라 공통조상까지의 도로의 길이 중 최댓값/최솟값도 알아야 했고

여기저기 헷갈린 탓인지 여러 차례 틀려서 힘들었다ㅠ

 

---

 

1. Get P

 

먼저 각 도시의 1, 2, 4, 8, ...번째 조상을 조사한다.

1을 root로 하여 BFS로 탐색하고, 조상을 탐색하며 도로 길이의 최소/최대를 구한다.

 

P[ i ][ k ]

r = 도시 i의 $2^{\mathrm{k}}$번째 조상

mn = i부터 조상까지의 최소 도로 길이

mx = i부터 조상까지의 최대 도로 길이

	Q.push(1), dep[1] = 1;
	while (!Q.empty()) {
		int prv = Q.front(); Q.pop();

		for (road r : R[prv]) {
			if (dep[r.v]) continue;
			int cur = r.v; Q.push(cur);

			dep[cur] = dep[prv] + 1;
			P[cur][0] = { prv, r.c, r.c };
			for (int k = 0; k < 17; ++k) {
				if (!P[P[cur][k].v][k].v) break;
			
				P[cur][k + 1].v = P[P[cur][k].v][k].v;
				P[cur][k + 1].mn = min(P[cur][k].mn, P[P[cur][k].v][k].mn);
				P[cur][k + 1].mx = max(P[cur][k].mx, P[P[cur][k].v][k].mx);
			}
		}
	}

• DFS로 해도 된다. 그러나 큐를 써도 BFS가 더 빨랐다.
• 트리만 구축하고 for문으로 돌려도 된다. 그러나 BFS내부에서 처리하는 게 더 빨랐다.

 

 

2. Get ANS

이제 입력을 받으며 도시 d, e에 대한 답 minn, maxx를 구한다.

먼저 두 도시의 depth가 다르면 같게 해주면서 minn, maxx를 업데이트하고

두 도시의 depth가 동일해지면 LCA를 찾아 minn, maxx를 업데이트한다.

	int minn = INF;
	int maxx = 0;
	if (dep[d] > dep[e]) swap(d, e);
        
	// 1.  Make Depth Same
	for (int k = 17; k >= 0; --k) {
		if (dep[e] - dep[d] >= (1 << k)) {
			minn = min(minn, P[e][k].mn);
			maxx = max(maxx, P[e][k].mx);
			e = P[e][k].v;
		}
	}
        
	// 2. Find LCA
	if (d != e) {
		for (int k = 17; k >= 0; --k) {
			if (P[d][k].v == P[e][k].v) continue;
			minn = min(minn, min(P[d][k].mn, P[e][k].mn));
			maxx = max(maxx, max(P[d][k].mx, P[e][k].mx));
			d = P[d][k].v, e = P[e][k].v;
		}
		minn = min(minn, min(P[d][0].mn, P[e][0].mn));
		maxx = max(maxx, max(P[d][0].mx, P[e][0].mx));
	}

• minn, maxx먼저 업데이트한 뒤에 d, e를 업데이트 해야 한다.
• 2의(line 15-24)
  for문(line 16-21)에서는 d의 부모와 e의 부모가 다를 때만 업데이트하므로
  for문이 끝난 후(line 22-23) minn과 maxx를 한 번 더 업데이트 해야 한다.
• example.
  아래 오른쪽 그림에서 d=9 e=2이면
  line 6-12:   d=6 e=2
  line 16-21: d=5 e=3 이므로
  line 22-23 에서 minn, maxx를 한 번 더 업데이트 해줘야 한다.

 

 

---

 

전체 코드

 

R[ i ]  도시 i의 도로 정보

P[ i ][ k ]  도시 i의 $2^{\mathrm{k}}$번째 조상에 대해 조사

dep[ i ]  도시 i의 depth (dep[1]=1 기준)

 

#include <cstdio>
#include <queue>
#include <algorithm>
#define INF 1000001
using namespace std;

struct road{
	int v, c;
};
vector<road> R[100001];
struct parent {
	int v, mn = INF, mx = 0;
};
parent P[100001][18];
int dep[100001];
queue<int> Q;

void GetP() {
	Q.push(1), dep[1] = 1;
	while (!Q.empty()) {
		int prv = Q.front(); Q.pop();

		for (road r : R[prv]) {
			if (dep[r.v]) continue;
			int cur = r.v; Q.push(cur);

			dep[cur] = dep[prv] + 1;
			P[cur][0] = { prv, r.c, r.c };
			for (int k = 0; k < 17; ++k) {
				if (!P[P[cur][k].v][k].v) break;

				P[cur][k + 1].v = P[P[cur][k].v][k].v;
				P[cur][k + 1].mn = min(P[cur][k].mn, P[P[cur][k].v][k].mn);
				P[cur][k + 1].mx = max(P[cur][k].mx, P[P[cur][k].v][k].mx);
			}
		}
	}
}
int main() {
	int N, K, a, b, c, d, e;
	scanf("%d", &N);
	for (int i = 1; i < N; ++i) {
		scanf("%d%d%d", &a, &b, &c);
		R[a].push_back({ b,c }); R[b].push_back({ a,c });
	}

	GetP();

	scanf("%d", &K);
	while (K--) {
		scanf("%d%d", &d, &e);

		int minn = INF;
		int maxx = 0;
		if (dep[d] > dep[e]) swap(d, e);
        
        for (int k = 17; k >= 0; --k) {
			if (dep[e] - dep[d] >= (1 << k)) {
				minn = min(minn, P[e][k].mn);
				maxx = max(maxx, P[e][k].mx);
				e = P[e][k].v;
			}
		}
        if (d != e) {
			for (int k = 17; k >= 0; --k) {
				if (P[d][k].v == P[e][k].v) continue;
				minn = min(minn, min(P[d][k].mn, P[e][k].mn));
				maxx = max(maxx, max(P[d][k].mx, P[e][k].mx));
				d = P[d][k].v, e = P[e][k].v;
			}
			minn = min(minn, min(P[d][0].mn, P[e][0].mn));
			maxx = max(maxx, max(P[d][0].mx, P[e][0].mx));
		}
		printf("%d %d\n", minn, maxx);
	}
	return 0;
}
/*
12
1 5 20 1 3 10 3 2 100 3 4 200 2 12 60
5 6 40 6 7 50 6 8 70 8 9 200 8 11 110 9 10 120
10
10 6
11 3
*/