[BOJ 1167번/C++] 트리의 지름

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

1167번: 트리의 지름

트리의 지름

문제

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

 

풀이

앞서 풀었던 1967번 트리의 지름을 구하는 문제에서, 입력 형식만 변형된 문제였다!

 

입력을 받는 것에 조금 고민이 필요해서 그런지, 1967번(골드4)에 비해 조금 높은 티어(골드2)를 배정받았다.

그렇다고 푸는 방법은 변하지 않기 때문에, -1이 나오기 전 까지는 입력을 유지해야한다는 점을 잘 해결하면, 풀이에 큰 어려움은 없었다.

 

마찬가지로 이 문제도! DFS를 한 번 사용해서(이 때는 1에서 시작한다.), 가장 멀리 있는 노드를 찾는다.

이번에는 가장 멀리 있는 노드에서 시작해, DFS를 한 번 더 사용해서 각 노드까지의 거리 중 최대 거리를 찾는다.이 때 구한 거리가 트리의 지름이 된다. 

 

#include <iostream>
#include <vector>
#include <queue>

#define endl '\n'

using namespace std;

vector<pair<int, int>> tree[100001];
bool visited[100001];
int max_node;
int max_dist;

void DFS(int node, int dist) {
    if (max_dist < dist) {
        max_dist = dist;
        max_node = node;
    }

    visited[node] = true;

    for (int i = 0; i < tree[node].size(); i++) {
        if (!visited[tree[node][i].first]) {
            DFS(tree[node][i].first, tree[node][i].second + dist);
        }
    }
}

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

    int V;
    cin >> V;

    int a, b = -2, c;
    for (int i = 0; i < V; i++) {
        cin >> a;
        cin >> b;
        while (b != -1) {
            cin >> c;
            tree[a].push_back({ b, c });
            cin >> b;
        }
    }

    DFS(1, 0);
    max_dist = 0;
    for (int i = 1; i <= V; i++)
        visited[i] = false;
    DFS(max_node, 0);

    cout << max_dist << endl;

    return 0;
}