1167번: 트리의 지름

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

1167번: 트리의 지름

1. 트리의 루트 노드에서 가장 거리가 먼 노드 a에 대해, 노드 a로부터 가장 거리가 먼 노드 b까지의 거리가 트리의 지름이 된다.

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> edge;

#define MAX 100001
#define _node first
#define _dist second

int N, ret = 0;
edge ans = { 0, 0 };
vector<edge> tree[MAX];

int max(int a, int b) { return a > b ? a : b; }

// 루트 노드에서 부모 노드가 parent인 노드 node까지의 거리가 dist일 때
// node에서 리프 노드까지의 거리를 계산
void dfs(int node, int parent, int dist) {
    // node의 자식 노드에서 dfs를 실행
    for (auto e : tree[node]) if (e._node != parent)
        dfs(e._node, node, dist + e._dist);

    // 이전까지 찾아낸 거리보다 현재 거리가 더 멀다면
    // 현재 노드와 거리를 루트 노드에서 가장 먼 노드와 그 거리로 설정
    if (ans._dist < dist) ans = { node, dist };
}

int main () {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // N: 노드의 수, node: 연결된 노드를 입력받을 때 쓸 각 노드의 인덱스
    // child: 각 노드와 연결된 자식 노드, dist: 노드와 노드 사이의 거리
    int N, node, child, dist;

    // 트리를 입력받은 뒤
    cin >> N;
    while (N--) {
        cin >> node >> child;
        while (child != -1) {
            cin >> dist;
            tree[node].push_back({child, dist});
            cin >> child;
        }
    }
    // 임의의 노드로부터 가장 거리가 먼 노드를 구하고
    dfs(1, 0, 0);
    // 그 노드로부터 가장 거리가 먼 노드와의 거리를 구해 출력한다
    dfs(ans._node, ans._node, 0);
    printf("%d\n", ans._dist);

    return 0;
}

 

 

2. 트리에서 루트 노드와 리프 노드까지의 거리를 반지름이라 하면, 이 문제에서 구하고자 하는 답은 가장 긴 두 반지름의 합이다. 이 반지름은 루트의 자식 노드를 루트 노드로 갖는 서브 트리의 반지름과 루트 노드에서 자식 노드까지의 거리의 합으로 구할 수 있으므로, dfs를 이용해 구현 가능하다.

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> edge;

#define MAX 100000
#define _node first
#define _dist second

// 트리의 최대 지름
int ans = 0;
// tree[i]: 노드 i와 연결된 에지(들)
vector<edge> tree[MAX + 1];

void swap(int &a, int &b) { int temp = a; a = b; b = temp; }
void set_max(int &a, int b) { a = a > b ? a : b; }

int dfs(int node, int parent) {
    // node의 자식 노드를 루트로 삼는 서브 트리의 반지름 중 가장 긴 두 반지름
    int dist[2] = { 0, 0 };

    // node의 자식 노드에 대해
    for (edge e : tree[node]) if (e._node != parent) {
        // 각 서브 트리의 가장 긴 반지름을 
        // 현재 트리의 두 번째로 긴 반지름과 비교하여 갱신
        set_max(dist[1], dfs(e._node, node) + e._dist);
        // 가장 긴 두 반지름을 비교하여 정렬
        if (dist[0] < dist[1]) swap(dist[0], dist[1]);
    }

    // 트리의 지름을 두 반지름의 합과 비교하여 갱신
    set_max(ans, dist[0] + dist[1]);
    // 가장 긴 반지름을 반환
    return dist[0];
}

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, node, child, dist;
    
    // 트리를 입력받는다
    cin >> N;
    while (N--) {
        cin >> node >> child;
        while (child != -1) {
            cin >> dist;
            tree[node].push_back({child, dist});
            cin >> child;
        }
    }

    // 트리의 지름 계산
    dfs(1, 0);
    // 계산한 트리의 지름을 출력한다
    cout << ans << '\n';

    return 0;
}
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> edge;

#define MAX 100000
#define _node first
#define _dist second

// 트리의 최대 지름
int ans = 0;
// tree[i]: 노드 i와 연결된 에지(들)
vector<edge> tree[MAX + 1];

void swap(int &a, int &b) { int temp = a; a = b; b = temp; }
void set_max(int &a, int b) { a = a > b ? a : b; }

int dfs(int node, int parent) {
    // node의 자식 노드를 루트로 삼는 서브 트리의 반지름 중 가장 긴 두 반지름
    int dist[2] = { 0, 0 };

    // node의 자식 노드에 대해
    for (edge e : tree[node]) if (e._node != parent) {
        // 각 서브 트리의 가장 긴 반지름을 
        // 현재 트리의 두 번째로 긴 반지름과 비교하여 갱신
        set_max(dist[1], dfs(e._node, node) + e._dist);
        // 가장 긴 두 반지름을 비교하여 정렬
        if (dist[0] < dist[1]) swap(dist[0], dist[1]);
    }

    // 트리의 지름을 두 반지름의 합과 비교하여 갱신
    set_max(ans, dist[0] + dist[1]);
    // 가장 긴 반지름을 반환
    return dist[0];
}

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, node, child, dist;
    
    // 트리를 입력받는다
    cin >> N;
    while (N--) {
        cin >> node >> child;
        while (child != -1) {
            cin >> dist;
            tree[node].push_back({child, dist});
            cin >> child;
        }
    }

    // 트리의 지름 계산
    dfs(1, 0);
    // 계산한 트리의 지름을 출력한다
    cout << ans << '\n';

    return 0;
}