[백준] 1967번 : 트리의 지름

문제

 

---

풀이

 

그림에 답이 있다.

오른쪽 그림의 회색 점들 중에서 아무거나 하나를 찍어보자.

그리고 그 회색점에서 가장 멀리있는 점을 찾아보자. 어떤 회색점을 골라도 두 개의 파란점 중 하나가 선택될 것이다.

 

그렇다면 아무 점이나 하나 고르고, 그 점과 가장 먼 점을 고르면 그건 지름을 구성하는 2개의 점 중 하나인 것이다.

그러면 이렇게 구한 점 하나에 대해 또 가장 멀리 있는 점을 고르면 그 점은 지름을 구성하는 또다른 점인 것이다.

그 둘 사이의 거리가 지름이다.

 

이걸 구현하기 위해 dfs를 2번 사용할 것이다.

첫번째 dfs로 지름을 구성하는 점 중 하나를 찾고, 두번째 dfs로 트리의 지름을 찾는다.

 

거리를 dfs로 구해도 되는지 걱정될 수도 있다.

근데 트리의 특징 중 하나는 특정 정점 2개를 연결하는 경로가 단 1개라는 것이다. 사이클이 없기 때문이다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

typedef pair<int, int> pp;

vector<vector<pp>> graph;
vector<pp> status; //first=거리, second=방문여부
int max_diameter, node;

void dfs(int cur) {
    for (int i = 0; i < graph[cur].size(); i++) {
        int dest = graph[cur][i].first;
        if (status[dest].second == 0) { //미방문 정점
            status[dest].second = 1; //방문 처리
            status[dest].first = status[cur].first + graph[cur][i].second; //거리 갱신
            if (max_diameter < status[dest].first) { //최대 지름보다 크다면 갱신
                max_diameter = status[dest].first;
                node = dest;
            }
            dfs(dest); //dfs 호출
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, p, c, w;

    cin >> n;
    graph.assign(n + 1, vector<pp>(0));
    for (int i = 1; i < n; i++) {
        cin >> p >> c >> w;
        graph[p].push_back(make_pair(c, w));
        graph[c].push_back(make_pair(p, w));
    }
    status.assign(n + 1, make_pair(0, 0)); //1에 대한 dfs를 한 뒤, 1과 제일 먼 node를 구함
    status[1].second = 1;
    dfs(1);

    status.assign(n + 1, make_pair(0, 0)); //node에 대한 dfs
    status[node].second = 1;
    dfs(node);

    cout << max_diameter << '\n';
}

전체 소스코드다.

 

    status.assign(n + 1, make_pair(0, 0)); //1에 대한 dfs를 한 뒤, 1과 제일 먼 node를 구함
    status[1].second = 1; //방문처리
    dfs(1);

먼저 그냥 간단하게 정점 1에 대한 dfs를 한다.

 

void dfs(int cur) {
    for (int i = 0; i < graph[cur].size(); i++) {
        int dest = graph[cur][i].first;
        if (status[dest].second == 0) { //미방문 정점
            status[dest].second = 1; //방문 처리
            status[dest].first = status[cur].first + graph[cur][i].second; //거리 갱신
            if (max_diameter < status[dest].first) { //최대 지름보다 크다면 갱신
                max_diameter = status[dest].first;
                node = dest;
            }
            dfs(dest); //dfs 호출
        }
    }
}

정점 1에 대한 모든 정점까지의 거리를 갱신하면서 dfs를 실행한다.

최대 거리가 갱신될 때면 해당 정점을 node 변수에 저장한다.

 

    status.assign(n + 1, make_pair(0, 0)); //node에 대한 dfs
    status[node].second = 1; //방문처리
    dfs(node);

dfs 이후 node 변수에는 트리의 지름 중 하나의 정점이 들어왔을 것이다.

node에 대한 dfs를 실행한다.

 

    cout << max_diameter << '\n';

지름을 출력하면 된다.