[백준]3176 도로 네트워크

[정답이 아니라 풀이 기록입니다.]

도로 네트워크

N개의 도시가 N-1개의 간선으로 두 도시간 경로가 유일하게 연결되어있다. 두 도시쌍이 여러개 들어올 때 두 도시를 연결하는 도로중 가장 긴 도로와 가장 짧은 도로를 구하시오.

접근

1. 도로는 당연히 양방향입니다.
2. 오로지 a,b 두 도시 사이의 경로만 고려해야합니다.
3. dfs로 찾기에는 너무 오래 걸립니다.

구현

LCA

이 문제에서는 두 도시 사이의 경로가 필요 한 것이 아니라, 두 도시 사이의 경로에서 가장 긴 도로와 가장 짧은 도로만 뭔지 알아내면 됩니다.
트리 구조의 도로 네트워크에서 a->b의 경로는 a -> a와 b의 최소공통조상 -> b가 됩니다.
그렇기에 a와 (a와 b의 최소 공통 조상) 사이의 최장, 최단 도로를 구하고 b와 (a와 b의 최소공통 조상)사이의 최장, 최단을 구해 두개를 비교해서 출력하면 됩니다.
LCA(최소공통조상)를 구현해봅시다.

LCA의 기본은 아래와 같습니다.

1. 임의의 노드를 루트를 잡고 루트의 깊이를 0, 루트의 자식의 깊이를 1, 그 노드의 자식을 2... 이런식으로 DFS를 통해 깊이를 구한다.
2. 두 노드번호가 들어오면 두 노드의 깊이를 비교한 후, 깊이가 깊은 노드를 깊이가 얕은 노드와 같은 깊이가 될때까지 부모를 따라 올라간다.
3. 깊이가 같아졌다면 두 노드가 같은 번호가 될때까지 둘 다 부모를 따라 올라간다.
4. 노드번호가 같아졌다면 그 노드가 LCA다.

그런데 생각해보면 이 문제에서는 n이 10만개 들어옵니다.

1. (1이 루트) 1-2-3-4...-99999-100000 와 같이 일직선에서 1, 100000이 들어온다면?
   -> 2번을 통해 같은 깊이로 맞추는데 10만개의 노드를 방문해야합니다.
2. (5만이 루트) 50000에서 갈라져서 왼쪽은 49999-49998로 감소해서 1이 되고 오른쪽은 50001-50002로 증가해서 10만이 되는 그래프에서 1,10만이 들어온다면?
   ->3번을 통해 LCA를 찾는데 10만개의 노드를 방문해야합니다.

느립니다.
부모로 빠르게 올라가는 방법을 찾아야하는데 희소배열을 사용하면 빠른 속도로 올라 갈 수 있습니다.

빠른 LCA

->희소배열의 설명이 적혀있는 문제(링크)
희소배열의 설명은 위 문제에서 했기에 생략하겠습니다.

1. 깊이 구하기

void dfs(int node) {
	check[node] = true;
	for (int i = 0; i < v[node].size(); i++){
		if (!check[v[node][i]]) {
			table[0][v[node][i]] = node
			dfs(v[node][i]);
		}
	}
}
void make_table(){
	for (int i = 1; i <= 17; i++) {
			for (int j = 1; j <= n; j++) {
				table[i][j]= table[i-1][table[i-1][j]]t;
			}
	}
}

희소배열을 생성하는 코드 두개입니다. 위에서 table[0]을 아래에서 table[1~n]을 구하는데
table[0]을 구하는 김에 LCA에 필요한 깊이도 구하게 변경합니다.

void dfs(int node) {
	check[node] = true;
	for (int i = 0; i < v[node].size(); i++){
		if (!check[v[node][i]]) {
			table[0][v[node][i]] = node
            depth[v[node][i]] = depth[node] + 1;//깊이 구하기
			dfs(v[node][i]);
		}
	}
}

2. 깊이 맞추기

두 노드 번호가 들어오면 깊이가 깊은 쪽을 얕은 쪽 번호와 같아지게 올려야합니다.
이때 몇 번째 부모로 이동할지는 비트를 통해 구할 수 있습니다.

a = 깊이 13 = 1101
b = 깊이 3 = 0011
1101 - 0011 = 13 - 3 = 1010 = 10
a의 2번째 부모의 8번째 부모로 a를 올리면 깊이 같아짐

if (depth[a] > depth[b]) {
			int c = depth[a] - depth[b];//차 구하기
			int Count = 0;//2^Count번째 부모를 나타낼 때 사용
			while (c > 0) {
				if ((c & 1) == 1) {//만약 가장 앞 비트가 1이라면
					a = table[Count][a];//2^Count번째 부모로 올라감
				}
				c = c >> 1;//c의 비트를 한칸씩 앞으로 당김
				Count++;//Count 증가
			}
		}

		if (depth[b] > depth[a]) {//이하 같음
			int c = depth[b] - depth[a];
			int Count = 0;
			while (c > 0) {
				if ((c & 1) == 1) {
					b = table[Count][b];
				}
				c = c >> 1;
				Count++;
			}
		}

3. 올리기

깊이를 맞췄을때 두 노드가 같아지는 경우가 있습니다. 그 경우는 3번을 생략합니다.
아래는 깊이를 맞춘 뒤 두 노드가 다른 경우입니다.

임의의 두 노드 a,b에서 최소공통조상 이후로는 계속 올라가도 조상이 같습니다.
그렇기에 단순히 조상이 같다고 이것이 최소공통조상이다! 할 수는 없습니다.
그래서 공통조상이 아닌 노드까지 두 노드를 계속 올립니다. 이후에 한칸을 올리게 되면 그 노드가 최소공통 조상이 되기에 이런 방식으로 최소공통조상을 찾습니다.

공통조상이 아닌 노드까지 계속 올려봅시다.

일단 위의 희소배열글에서 적혀있던 것이 있습니다.

i번 노드에서 2^(17-1) 번째 부모로 이동할 수 없고 2^(16-1) 번째로 이동이 가능하다면 2^(16-1)번째 부모노드로 이동해 2^(15-1), 2^(14-1), ...로 쭈르륵 부모 따라 이동해도 2^(17-1)보다 멀리가지 못합니다.

1000 > 0111

그렇기 때문에 모든 노드에서 부모의 이동은 17~0까지 한번의 루프만 돌면 됩니다.

이것은 여기에도 적용이 됩니다.
table[17~0]까지 돌면서 만약 두 노드의 부모가 다르다면 올라가고 같다면 그대로 있으면 됩니다.

if (a != b) {
		for (int i = 17; i >= 0; i--) {
			if (table[i][a].first != table[i][b].first) {
				a = table[i][a];
				b = table[i][b];
			}
		}
		a = table[0][a];
		b = table[0][b];
}

for문이 끝나고 나면 a와 b는 최소공통조상의 자식에 위치하게 됩니다.
그렇기에 table[0]을 통해 한칸 올라가게 되면 a와 b는 최소공통조상을 가리키게 됩니다.

4. LCA 출력

2번,3번에서 4번으로 넘어왔다면 a와 b는 같은 노드를 가리킵니다.
그것이 LCA이고 출력하면 됩니다.

printf("%d",a);

여기까지 구현하셨다면

또 다른 문제(링크) 를 풀 수 있습니다.
여기에 이 문제에서는 도로의 최대, 최소 길이를 구해야합니다.

최대 최소 구하기

간선에 가중치가 붙고, table에 최대, 최소를 저장해야하기에 table과 vector의 정의를 약간 바꿉니다.

vector<pair<int,long long>> v[100002] //노드번호와 가중치
pair<int,pair<long long,long long>>table[18][100002];//2^n번 부모의 번호,2^n번 부모까지의 최대, 최소

DFS와 테이블을 만드는 부분에서도 최대, 최소를 저장하게 변경합니다.

이때 DFS에서 바로 위 1번째 부모는 최대와 최소가 같습니다.

그리고 테이블을 만드는 부분은 i번 노드에서 4번째 부모까지의 최대 최소 = (i번 노드에서 2번째 부모까지의 최대 최소, i번 노드의 2번째 부모에서 2번째 부모까지의 최대 최소) 중 최대, 최소 이런 식으로 이루어집니다.

void dfs(int node) {
	check[node] = true;
	for (int i = 0; i < v[node].size(); i++) {
		if (check[v[node][i].first] == false) {
			depth[v[node][i].first] = Rank[node]+1;
			table[0][v[node][i].first] = {node,{v[node][i].second,v[node][i].second}};//최대 최소 저장
			dfs(v[node][i].first);
		}
	}
}

void make_table() {
	for (int i = 1; i <= 16; i++) {
		for (int j = 1; j <= n; j++) {
			table[i][j] = {table[i-1][table[i-1][j].first].first,//노드 번호
				{ 
				  max(table[i-1][j].second.first,table[i-1][table[i-1][j].first].second.first),//최대
				  min(table[i - 1][j].second.second,table[i - 1][table[i - 1][j].first].second.second)//최소
				}
			};
		}
	}
}

그리고 이제 3번고 4번과정에서 부모노드로 올라갈 때, (현재의 최대 최소,올라가는 과정에서 최대 최소)중 최대 최소를 저장하도록 코드를 추가합니다.

ll MaxA = 0;
ll MinA = MAX;
ll MaxB = 0;
ll MinB = MAX;
//-----------------------------------------------
if (depth[a] > depth[b]) {
		int c = depth[a] - depth[b];
		int Count = 0;
		while (c > 0) {
			if ((c & 1) == 1) {
				MaxA = max(MaxA,table[Count][a].second.first);
				MinA = min(MinA,table[Count][a].second.second);
				a = table[Count][a].first;
			}
			c = c >> 1;
			Count++;
		}
}

//--------------------------------------------

if (a != b) {
		for (int i = 17; i >= 0; i--) {
			if (table[i][a].first != table[i][b].first) {
				MaxA = max(MaxA, table[i][a].second.first);
				MinA = min(MinA, table[i][a].second.second);
				MaxB = max(MaxB, table[i][b].second.first);
				MinB = min(MinB, table[i][b].second.second);
				a = table[i][a].first;
				b = table[i][b].first;
			}
		}

		MaxA = max(MaxA, table[0][a].second.first);
		MinA = min(MinA, table[0][a].second.second);
		MaxB = max(MaxB, table[0][b].second.first);
		MinB = min(MinB, table[0][b].second.second);
		a = table[0][a].first;
		b = table[0][b].first;
}

저는 a와 b를 나눠 최대 최소를 구했지만 하나로 해도 됩니다.

답 출력

위의 과정이 끝나고나면 a와 b를 나눴다면 MaxA,MaxB에 최대,MinA,MinB에 최소가 저장되어있고
나누지 않았다면 Max에 최대 Min에 최소가 저장되어 있을 것입니다.
전자라면 아래와 같이 출력하고

printf("%lld %lld\n",min(MinA,MinB),max(MaxA,MaxB));

후자라면 아래와 같이 출력하면 됩니다.

printf("%lld %lld\n",Min,Max);

마무리

O(nlogn) LCA을 알고있다면 쉽게 풀 수 있는 문제인 것 같습니다.
구조체로 table을 선언했다면 좀 더 깔끔했을 것 같긴하네요.

끝!