[BOJ] 19581 두 번째 트리의 지름 C++

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

19581번: 두 번째 트리의 지름

트리의 지름을 구하는 것을 응용한 문제이다. 아래 문제를 먼저 풀고 들어오면 괜찮을 것 같다.

https://coderecord.tistory.com/9

[BOJ] 1167 트리의 지름 C++

첫번째 트리의 지름을 구하는 문제 알고리즘을 구하는 방식을 응용하여 나는 두번째 트리를 구하는 알고리즘을 다음과 같이 세웠다.

1. 임의의 점에서 가장 긴 거리를 갖는 리프노드와 두번째로 긴 거리를 갖는 리프노드를 찾는다.

2. 첫번째로 긴 거리를 갖는 리프노드를 루트노드로 정하고 두번째로 큰 거리를 구한다.

3. 두번째로 긴 거리를 갖는 리프노드를 루트노드로 정하고 구한 가장 큰 거리를 구한다.

4. 두 값을 비교한다.

이렇게 구현을 했는데 84%에서 뜨는 틀렸습니다... PS가 참 밉다...

 

어김없이 다른 분들의 코딩을 찾아봤는데 내가 2가지 경우를 빼먹었다.

1. 두번째로 긴 거리를 갖는 리프노드를 루트노드로 정하였을 때 가장 큰 거리가 첫번째로 긴 거리를 갖는 리프노드라면 제일 큰 경우가 돼버린다. 그래서 첫번째로 긴 거리를 갖는 리프노드는 제외하고 dfs를 돌려야 한다.

2. 제일 큰 지름에서 양 끝 노드들 중 하나를 뺀 것이 두번째로 큰 지름인 경우이다.

 

따라서 위 조건을 추가하려면 알고리즘을 다음과 같이 짜야한다.

1. 임의의 점에서 첫번째로 긴 거리를 갖는 리프노드(idx1)를 루트노드로 정하고 가장 긴 거리를 갖는 리프노드(idx2)를 찾는다.

2. idx1을 루트노드로 정하고 idx2를 제외 시킨 뒤에 dfs를 돌려 최댓값을 찾는다.

3. idx2를 루트노드로 정하고 idx1을 제외 시킨 뒤에 dfs를 돌려 최댓값을 찾는다.

4. 두 값중 최댓값이 두번째 지름이 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
bool check[100001];
vector<pair<int,int> > v[100001];
int m=0;
int ans1=0;
int N;
void dfs(int start,int dist_sum){
    check[start]=true;
    bool flag=false;
    int size=v[start].size();
    int result=0;
    for(int i=0;i<size;i++){
        int go=v[start][i].first;
        int dist=v[start][i].second;
        if(!check[go]){
            dfs(go,dist_sum+dist);
            flag=true;
        }
    }
    check[start]=false;
    if(flag) return;
    if(m<dist_sum){
        m=dist_sum;
        start_idx1=start;
    }
}
void dfs2(int start,int dist_sum){
    check[start]=true;
    bool flag=false;
    int size=v[start].size();
    int result=0;
    for(int i=0;i<size;i++){
        int go=v[start][i].first;
        int dist=v[start][i].second;
        if(!check[go]){
            dfs2(go,dist_sum+dist);
            flag=true;
        }
    }
    check[start]=false;
    if(flag) return;
    if(m<dist_sum){
        m=dist_sum;
        start_idx2=start;
    }
}
void dfs3(int start,int dist_sum){
    check[start]=true;
    bool flag=false;
    int size=v[start].size();
    for(int i=0;i<size;i++){
        int go=v[start][i].first;
        int dist=v[start][i].second;
        if(!check[go]){
            flag=true;
            dfs3(go,dist_sum+dist);
        }
    }
    check[start]=false;
    if(flag) return;
    ans1=max(ans1,dist_sum);
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    cin>>N;
    for(int i=0;i<N-1;i++){
        int from,to,dist;
        cin>>from>>to>>dist;
        v[from].push_back(make_pair(to,dist));
        v[to].push_back(make_pair(from,dist));
    }
    dfs(1,0);     // 가장 긴 지름의 한 점을 구한다.
    m=0;
    dfs2(start_idx1,0); // 가장 긴 지름의 양 끝을 구한다.
    check[start_idx2]=true; // 가장 긴 점 중 한점을 제외하고 최댓값을 구한다.
    dfs3(start_idx1,0);
    check[start_idx2]=false;
    check[start_idx1]=true; // 가장 긴 점 중 다른 한점을 제외하고 최댓값을 구한다.
    dfs3(start_idx2,0);
    cout<<ans1;
    return 0;
}