Boj 1967 & 19581 c++ 트리의 지름 + 두 번째 지름

https://www.acmicpc.net/problem/1967

https://www.acmicpc.net/problem/19581

이제 DFS문제이다. 두 문제 모두 '트리의 지름'이라는 개념을 다루고 있다. 

 

*트리의 지름이란?

트리는 기본적으로 n개의 노드들과 n-1개의 간선들로 이루어져있다. 때문에 순환하지 않고 한쪽에서 시작해서 다른 한쪽에서 끝날 수 있다. 이때 지름은 트리 내에서 가장 먼 두 정점 사이의 거리를 뜻한다. 두 정점을 기준으로 트리를 펼쳤을 때, 다른 정점들은 트리의 지름을 지름을 지름으로 한 원 내에 모두 들어온다.

 

이때 트리의 지름을 구하는 방법은 간단하다. 임의의 정점에서 가장 먼 다른 정점 하나를 구하고, 이를 farthest_nod에 저장한다. 그 이후, 그 정점에서 다시 가장 먼 정점을 구하고, 그곳까지의 거리를 저장한다. 이때, 그 거리는 트리의 지름이 된다. 간선에 가중치가 있을 때, 없을 때 모두 구하는 방법이 같다.

 

이때, 1967번에 대해 제출한 코드는 다음과 같다.

#include<iostream>
#include<vector>

using namespace std;

vector<vector<pair<int, int>>> connected(10005);
vector<int> visited(10005);
long long sum;
long long Max=0;
int farthest_nod;

void DFS(int V){

   visited[V]=1;
   for(int i=0; i<connected[V].size(); i++){
        int next=connected[V][i].first;
        int weight=connected[V][i].second;
        if(!visited[next]){
            sum+=weight;
            DFS(next);
            if(sum>Max){
            Max=sum;
            farthest_nod=next;
            }
            sum-=weight;
        }
   }

}

int main(){

    int N;
    cin>>N;

    for(int i=1; i<N; i++){
         int v, u, w;
         cin>>v;
         cin>>u>>w;
         connected[v].push_back({u, w});
         connected[u].push_back({v, w});
    }

    DFS(1);
    for(int i=1; i<=N; i++){
    visited[i]=0;
    }
    sum=0;
    Max=0;
    DFS(farthest_nod);
    cout<<Max;

}

 

모든 정점에 대해서 DFS를 돌려 최대 길이를 구하는 것이 아닌 하나의 정점에서 가장 먼 곳을 기준으로 단 3번만 DFS를 시행한다는 점이 핵심이다.  

 

 

 

 

*트리의 두번째 지름이란?

트리의 지름이 되는 경로들 중 단 하나의 경우를 제외하고 가장 길이가 긴 경로의 길이를 '트리의 두번째 지름'으로 정의한다. 고로, 지름이 되는 경로가 두개 이상일때, 트리의 두번째 지름과 트리의 지름은 같아질 수 있다. 

 

여기서 한번 더 생각을 해보아야 한다.

 

'지름이 되는 경로를 제외하는 방법에는 무엇이 있을까?'

 

필자는 이 지점에서 여러 시행착오를 겪었다.

첫번째로 시도한 방법은 다음과 같았다.

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

vector<vector<pair<int, int>>> connected(100001);
vector<int> visited(100001);
queue<pair<int, int>> q;
long long Max=0;
long long sum;
bool found;
int farthest_node;


void DFS(int V){

   visited[V]=1;
   for(int i=0; i<connected[V].size(); i++){
        int next=connected[V][i].first;
        int weight=connected[V][i].second;
        if(!visited[next]){
            sum+=weight;
            DFS(next);
            if(sum>Max){
            Max=sum;
            farthest_node=next;}
            sum-=weight;
        }
   }

}
void DFS2(int V){

   visited[V]=1;
   for(int i=0; i<connected[V].size(); i++){
        int next=connected[V][i].first;
        int weight=connected[V][i].second;
        if(!visited[next]){
            q.push({V, next});
            sum+=weight;
            DFS2(next);
            if(sum==Max)
                found=true;
            if(!found)
                q.pop();
            sum-=weight;
        }
   }

}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin>>N;

    for(int i=1; i<N; i++){
         int v, u, w;
         cin>>v;
         cin>>u>>w;
         connected[v].push_back({u, w});
         connected[u].push_back({v, w});
    }

    DFS(1);
    Max=0;
    sum=0;
    fill(visited.begin()+1, visited.begin() + N + 1, 0);

    DFS(farthest_node);

    fill(visited.begin()+1, visited.begin() + N + 1, 0);
    sum=0;
     
    found=false;
    DFS2(farthest_node);
  
    


    long long Max_ans=0;
    while(!q.empty()){
        int v=q.front().first;
        int u=q.front().second;
        int w;
        for(int j=0; j<connected[v].size(); j++){
            if(connected[v][j].first==u){
                w=connected[v][j].second;
                connected[v].erase(connected[v].begin()+j); break;}
        }
        for(int j=0; j<connected[u].size(); j++){
            if(connected[u][j].first==v){
                connected[u].erase(connected[u].begin()+j); break;}
        }
        Max=0;
        sum=0;
        fill(visited.begin()+1, visited.begin() + N + 1, 0);
        DFS(u);
        long long ans=0;
        ans+=Max;
        fill(visited.begin()+1, visited.begin() + N + 1, 0);
        Max=0;
        sum=0;
        DFS(v);
        ans+=Max;
        Max_ans=max(Max_ans, ans);
        connected[v].push_back({u, w});
        connected[u].push_back({v, w});
        q.pop();
    }

    cout<<Max_ans;


}

 

 

 

우선 트리의 지름을 구하고, 그 경로를 벡터에 저장해 놓는다. 그리고 이후에 두번째 지름을 구하기 위해 경로에서 간선을 하나씩 삭제해가며 DFS를 돌린다. 이때, 간선이 삭제된 상태에서 경로를 탐색하므로 지름의 경로와 겹치지 않을 수 있다. 그 후, 길이 중에서 최대 만을 출력하면 그것이 두번째 지름의 길이가 된다고 생각했다. 예제에 대해서도 올바르게 작동했기에 해당 코를 제출해보았다.

 

결과는 당연하게도 시간초과였다. 모든 지점에 대해서 DFS를 돌리는 아이디어는 자연스럽게 시간복잡도를 증가시켰던 것이었다.

때문에, 다른 방법을 모색하게 되었다.

 

두번째 시도에는 구글링을 하여 코드의 논리를 개선하였다.

 

두번째 시도의 논리는 다음과 같다.

 

임의 정점에 대해 가장 먼 정점을 구하고 a로 저장한다. 그리고 a에서 가장 먼 정점을 b로 저장한다. 이때, a와 b는 트리의 지름의 양끝 점이 된다. 이 두 지점에서 각각 서로를 제외하고 가장 먼 지점까지의 거리를 fa, fb에 저장한다. 이때, fa와 fb중 더 큰 값이 두번째 지름이다. 

이 논리는 양 끝점에서만 연산을 진행함으로써 단 4번의 DFS 만으로 지름을 제외한 가장 긴 길이를 구해낼 수 있었다. 이를 구현한 코드는 다음과 같다.

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

vector<vector<pair<int, int>>> connected(100001);
vector<int> visited(100001);
queue<pair<int, int>> q;
long long Max=0, fa, fb;
long long sum;
int farthest_node, a, b, c;


void DFS(int V){

   visited[V]=1;
   for(int i=0; i<connected[V].size(); i++){
        int next=connected[V][i].first;
        int weight=connected[V][i].second;
        if(!visited[next]){
            sum+=weight;
            DFS(next);
            if(sum>Max){
            Max=sum;
            farthest_node=next;}
            sum-=weight;
        }
   }

}
void DFS2(int V){

   visited[V]=1;
   for(int i=0; i<connected[V].size(); i++){
        int next=connected[V][i].first;
        int weight=connected[V][i].second;
        if(!visited[next]&&next!=b){
            sum+=weight;
            DFS2(next);
            if(sum>Max){
            Max=sum;
            farthest_node=next;}
            sum-=weight;
        }
   }

}

void DFS3(int V){

   visited[V]=1;
   for(int i=0; i<connected[V].size(); i++){
        int next=connected[V][i].first;
        int weight=connected[V][i].second;
        if(!visited[next]&&next!=a){
            sum+=weight;
            DFS3(next);
            if(sum>Max){
            Max=sum;
            farthest_node=next;}
            sum-=weight;
        }
   }

}



int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin>>N;

    for(int i=1; i<N; i++){
         int v, u, w;
         cin>>v;
         cin>>u>>w;
         connected[v].push_back({u, w});
         connected[u].push_back({v, w});
    }

    DFS(1);
    a=farthest_node;
    Max=0;
    sum=0;
    for(int i=1; i<=N; i++){
        visited[i]=0;
    }

    DFS(farthest_node);
    b=farthest_node;
    Max=0;
    sum=0;
    for(int i=1; i<=N; i++){
        visited[i]=0;
    }
    DFS2(a);
    fa=Max;
    Max=0;
    sum=0;
    for(int i=1; i<=N; i++){
        visited[i]=0;
    }
    DFS3(b);
    fb=Max;

    cout<<max(fa, fb);




}