[정답이 아니라 풀이 기록입니다.]
N개의 도시가 N-1개의 간선으로 두 도시간 경로가 유일하게 연결되어있다. 두 도시쌍이 여러개 들어올 때 두 도시를 연결하는 도로중 가장 긴 도로와 가장 짧은 도로를 구하시오.
접근
- 도로는 당연히 양방향입니다.
- 오로지 a,b 두 도시 사이의 경로만 고려해야합니다.
- dfs로 찾기에는 너무 오래 걸립니다.
구현
LCA
이 문제에서는 두 도시 사이의 경로가 필요 한 것이 아니라, 두 도시 사이의 경로에서 가장 긴 도로와 가장 짧은 도로만 뭔지 알아내면 됩니다.
트리 구조의 도로 네트워크에서 a->b의 경로는 a -> a와 b의 최소공통조상 -> b가 됩니다.
그렇기에 a와 (a와 b의 최소 공통 조상) 사이의 최장, 최단 도로를 구하고 b와 (a와 b의 최소공통 조상)사이의 최장, 최단을 구해 두개를 비교해서 출력하면 됩니다.
LCA(최소공통조상)를 구현해봅시다.
LCA의 기본은 아래와 같습니다.
- 임의의 노드를 루트를 잡고 루트의 깊이를 0, 루트의 자식의 깊이를 1, 그 노드의 자식을 2... 이런식으로 DFS를 통해 깊이를 구한다.
- 두 노드번호가 들어오면 두 노드의 깊이를 비교한 후, 깊이가 깊은 노드를 깊이가 얕은 노드와 같은 깊이가 될때까지 부모를 따라 올라간다.
- 깊이가 같아졌다면 두 노드가 같은 번호가 될때까지 둘 다 부모를 따라 올라간다.
- 노드번호가 같아졌다면 그 노드가 LCA다.
그런데 생각해보면 이 문제에서는 n이 10만개 들어옵니다.
- (1이 루트) 1-2-3-4...-99999-100000 와 같이 일직선에서 1, 100000이 들어온다면?
-> 2번을 통해 같은 깊이로 맞추는데 10만개의 노드를 방문해야합니다.- (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을 선언했다면 좀 더 깔끔했을 것 같긴하네요.
끝!
