15. 트리 순회, 트리의 지름

15.md

0.00MB

0. 복습
1. 트리 순회

1991번을 보자.

전위 순회는 dfs한 순서대로 그대로 출력한다. (부모)(왼쪽자식)(오른쪽자식)

중위순회는 (왼쪽자식)(부모)(오른쪽자식) 이런식으로 출력된다.

후위순회는 (왼쪽자식)(오른쪽자식)(부모) 이런식으로 출력된다.

#include <iostream>
using namespace std;
char L[200], R[200];
void Pre(char n){
    cout << n;
    if(L[n]!='.') Pre(L[n]);

    if(R[n]!='.') Pre(R[n]); 

}
void In(char n){

    if(L[n]!='.') In(L[n]);
    cout << n;
    if(R[n]!='.') In(R[n]); 

}
void Post(char n){

    if(L[n]!='.') Post(L[n]);

    if(R[n]!='.') Post(R[n]); 
    cout << n;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N;   cin >> N;
    for(int i=0; i<N; ++i){
        char a, b, c;
        cin >> a >> b >> c;

        L[a] = b;
        R[a] = c;
    }
    Pre('A');
    cout << '\n';
    In('A');
    cout << '\n';
    Post('A');
    cout << '\n';
}

트리에서의 dfs는 visited가 없이도 구현이 가능하다.

어떤게 부모이고, 어떤게 자식인지 명확하게 알 수 있으면 단순 재귀로 하고,

명확하게 알지는 못하지만 어떤게 루트노드인지 알면 dfs에 이전 노드를 기억해주는 인자를 만들어준다.

17073번 코드는 다음과 같다.

///물의 양/리프 노드
#include <iostream>
#include <vector>
using namespace std;
vector<int> G[500001];
int leaves;
void dfs(int n, int prev){
    if(n!=1 && G[n].size()==1) {
        leaves++;
        return;
    }
    for(int i=0; i<G[n].size(); ++i){
        if(G[n][i]!=prev) dfs(G[n][i], n);
    }
}
int main(){
    int N, W; cin >> N >> W;
    for(int i=0; i<N-1; ++i){
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    cout << fixed;
    cout.precision(10);
    cout << (double)W/leaves << '\n';
}

참고 : 1991, 1068, 15900, 14675, 17073

2. 트리의 지름

그래프의 지름을 찾는건 어렵지만 트리는 쉽다.

(1) 아무 점이나 잡는다. 그 점을 a라고 한다.

(2) a에서 가장 먼 점 b를 찾는다.

(3) b에서 가장 먼 점 c를 찾는다.

(4) b와 c가 트리의 지름이다.

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

vector<pair<int, int> > G[10001];
int h[10001];

void DFS(int n, int prev){
    for(int i=0; i<G[n].size(); ++i){
        int next = G[n][i].first, cost = G[n][i].second;
        if(next != prev) {
            h[next]=h[n]+cost;
            DFS(next, n);
        }
    }
}

int main(){
    int n; cin >> n;
    for(int i=0; i<n-1; ++i){
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    DFS(1, 0);
    int mx = 1;
    for(int i=1; i<=n; ++i){
        if(h[mx]<h[i]) mx=i;
    }
    for(int i=0; i<=n; ++i){
        h[i]=0;
    }
    DFS(mx, 0);
    for(int i=1; i<=n; ++i){
        if(h[mx]<h[i]) mx=i;
    }
    cout << h[mx] << '\n';
}

O(N)의 시간복잡도를 갖는다.

하지만, 음수 가중치가 나왔을 때 이걸로 해결 못한다. dp를 사용하는 다른 풀이가 있다.

dp[n] : n에서 내려가면서 도달 가능한 최대 길이
dp[n] = max(dp[next] + cost)

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

int N, res;
vector<pair<int, int> > g[10101];
int dp[10101];

void DFS(int n, int prev){
    dp[n] = 0;
    vector<int> child;
    for(int i=0; i<g[n].size(); i++){
        int next = g[n][i].first, cost = g[n][i].second;
        if (next == prev) continue;

        DFS(next, n);
        dp[n] = max(dp[n], dp[next] + cost);
        child.push_back(dp[next] + cost);
    }
    sort(child.rbegin(), child.rend());
    if (child.size() == 0);
    else if (child.size() == 1){
        res = max(res, child[0]);
    }
    else if (child.size() >= 2){
        res = max(res, child[0] + child[1]);
    }
}

int main(){
    scanf("%d", &N);
    for(int i=0; i<N-1; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    DFS(1, 0);
    printf("%d", res);
    return 0;
}

참고 : 1967, 1167, 3584