[BOJ/C++] 20924: 트리의 기둥과 가지

🏅 GOLD 4

✏️ 1차 솔루션

⭐️ DFS 로 풀이

• 각 노드의 자식노드와 간선을 node struct 로 묶어서 저장
• 루트 노드부터 탐색 시작

1. 자식이 하나일 경우, 아직 기가노드를 찾기 전이라면 간선의 길이를 기둥에 더해주고 이어서 탐색
2. 자식이 2개 이상일 경우, 처음 2개 이상을 갖는 노드가 기가노드이므로 기가 노드 존재여부를 표기하고 DFS 로 가지의 길이를 구하기
3. 리프 노드에 도달하면 현재까지 계산한 가지를 최대값으로 갱신

🚨 1차 trouble

1. 그림의 설명처럼 위계가 정해져 있는 트리가 아니기 때문에 단방향 트리가 아니라 양방향 트리로 구현해야 하고 그에 따라서 방문한 노드를 다시 방문하지 않게끔 처리해주는 과정 필요
2. 나무의 몸통이 없이 루트 노드에서 바로 가지로 뻗어나가는 경우가 존재하기 때문에 몸통이 있는 경우와 없는 경우를 나눠서 계산해야 함

✏️ 최종 솔루션

1. 양방향 트리로 노드 저장
2. 몸통이 있는 경우: 연결된 노드가 2개(부모 노드와 자기 자신)보다 많을 때까지 몸통 길이 계산하고 가지 계산 시작 노드 값 저장
   몸통이 없는 경우: 몸통 길이 계산하는 과정 skip
3. 연결된 가지 길이 DFS 로 계산
   연결된 노드가 1개(부모 노드)만 남는 리프노드에 도달하면 최대 가지 길이 계산
   ❗️ 방문한 노드는 항상 방문 처리

📌 self feedback

트리는 양방향
예외처리 간과하지 말 것

✏️ 최종 code

#include <iostream>
#include <vector>

using namespace std;

struct node {
    int dst;
    int d;
};

vector<node> arr[2000001];
bool visit[2000001]={false};
int tr=0,br=0,cnt=0,st;

void find_trunk(int a) {

    if(arr[a].size()>2) {
        st=a;
        return;
    }
    
    visit[a]=true;
    
    for(int i=0;i<arr[a].size();i++) {
        node nd=arr[a][i];
        
        if(visit[nd.dst]) continue;
        
        tr+=nd.d;
        find_trunk(nd.dst);
    }
}

void find_branch(int a) {
    visit[a]=true;
    if(arr[a].size()==1) {
        br=max(cnt,br);
        return;
    }
    
    for(int i=0;i<arr[a].size();i++) {
        node nd=arr[a][i];
        
        if(visit[nd.dst]) continue;
        
        cnt+=nd.d;
        find_branch(nd.dst);
        cnt-=nd.d;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n,r,a,b,d;
    
    cin >> n >> r;
    
    for(int i=0;i<n-1;i++) {
        cin >> a >> b >> d;
        arr[a].push_back({b,d});
        arr[b].push_back({a,d});
    }
    
    // 몸통 없는 경우: 루트 노드의 자식이 여러개
    if(arr[r].size()>=2) st=r;
    else find_trunk(r);    // 몸통 있는 경우
    
    // 가지 길이 찾기
    find_branch(st);
    
    cout << tr <<" " << br;
}