[백준/C++] 20924번: 트리의 기둥과 가지(G4)

문제

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

20924번: 트리의 기둥과 가지

 

사용한 알고리즘

2022.02.05 - [PS/Algorithm] - [알고리즘 개념정리] 8. 그래프/그래프 탐색

2022.02.09 - [PS/Algorithm] - [알고리즘 개념정리] 9. 트리

 

풀이

bfs를 두 번 돌렸다.
bfs1은 트리의 기둥 길이 측정, bfs2는 가장 긴 가지의 길이를 측정한다.

<bfs1함수>
방문하지않은 연결된 노드 1개가 있으면 방문하고 dist를 갱신해준다.
현재 노드가 기가노드이면 트리의 기둥 길이(dist[cur])을 출력한다.

기가노드의 종류는 여러가지가 있다.
1. 연결된 노드가 3개인 경우(리프노드가 아닌 기가노드),
2. 리프노드이자 기가노드인 경우,
3. 루트노드이자 기가노드인(연결된 노드가 0개 또는 2개) 경우 이다. 

각각을 코드로 나타내면 다음과 같다.

int degree = adj[cur].size();

1. degree>=3
2. cur!=root && degree==1
3. cur==root && degree!=1

<bfs2함수>
기가노드부터 출발해서 가지들을 탐색한다.
노드를 방문할 때마다 dist와 max_dist를 갱신한다.

탐색이 끝나면 max_dist를 출력한다. 

 

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
typedef long long ll;

vector<pair<int,int>> adj[200001];
int visited[200001];
int dist[200001] = {0};
int N,R,a,b,d, Giga, max_dist;

void bfs1(int root){
    queue<int> q;
    q.push(root);
    visited[root]=1;

    while(!q.empty()){
        int cur = q.front(); q.pop();
        int degree = adj[cur].size();
        if(degree>=3 || (cur!=root && degree==1) || (cur==root && degree!=1)){
            //리프노드가 아닌 기가노드 || 리프노드인 기가노드 || 루트노드의 간선이 없거나 2개일때(루트노드가 기가노드)
            cout<<dist[cur]<<" ";
            Giga=cur;
            return;
        }
        for(pair<int,int> next:adj[cur]){
            if(visited[next.first]) continue;
            visited[next.first] = 1;
            q.push(next.first);
            dist[next.first]=dist[cur]+next.second;
        }
    }
}
void bfs2(int giga){
    queue<int> q;
    q.push(giga);
    visited[giga]=1;

    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(pair<int,int> next:adj[cur]){
            if(visited[next.first]) continue;
            visited[next.first] = 1;
            q.push(next.first);
            dist[next.first]=dist[cur]+next.second;
            max_dist=max(max_dist, dist[next.first]);
        }
    }
    cout<<max_dist;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>N>>R;
    for(int i=0; i<N-1; i++){
        cin>>a>>b>>d;
        adj[a].push_back({b,d});
        adj[b].push_back({a,d});
    }
    bfs1(R); //트리의 기둥 길이 측정

    visited[Giga]=0;
    dist[Giga]=0;
    bfs2(Giga); //트리의 가장 긴 가지의 길이 측정
    return 0;
}