[BOJ] 1167 : 트리의 지름

문제 링크

1167번: 트리의 지름 (acmicpc.net)

1167번: 트리의 지름

풀이

임의의 두 정점 사이의 거리중 가장 긴 거리를 찾는 문제

당연히 루트노드에서 탐색을 시작하면 가장 긴 거리를 찾을 수 있을 것이라 생각.

하지만 루트노드에서 탐색하면 모든 정점은 방문할 수 있겠지만 모든 경로를 탐색하지는 못했다.

그렇다고 모든 정점에서 부터 탐색을 할 것인가?? 그럼 시간초과가 난다.

해결

1. 루트노드에서 탐색을 시작해 가장 깊은 노드를 찾는다.

(여기서 가장 깊은 노드는 leaf 노드들 중 하나가 될 것이다.)

2. 그 가장 깊은 노드에서 다시 탐색을 시작한다.

이게 이 문제의 핵심이었다. 여기서 탐색은 깊이 우선 탐색을 말한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int,int>, int>, vector<pair<pair<int,int>, int>>, greater<pair<pair<int,int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100000 + 5;
int MAX;
int N;
vector<pair<int,int>> Edge[MAX_N];
bool visited[MAX_N];
int parent[MAX_N];
int leaf;
 
int Find(int x) {
    if (parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    int parent_x = Find(x);
    int parent_y = Find(y);
    parent[parent_x] = parent_y;
}
 
void dfs(int now, int distance) {
    visited[now] = true;
    if (distance > MAX) {
        MAX = distance;
        leaf = now;
    }
    for (int i = 0; i < Edge[now].size(); i++) {
        int next = Edge[now][i].first;
        int acost = Edge[now][i].second + distance;
        if (!visited[next])
            dfs(next, acost);
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 1; i <= N; i++)
        parent[i] = i;
 
    for (int i = 1; i <= N; i++) {
        int vertex;
        cin >> vertex;
        while (true) {
            int a, b;
            cin >> a;
            if (a == -1)
                break;
            cin >> b;
            Edge[vertex].push_back({ a,b });
            Union(vertex, a);
        }
    }
    dfs(Find(1), 0);
    memset(visited, 0, sizeof(visited));
    dfs(leaf, 0);
    cout << MAX << "\n";
    return 0;
}

여기서 Union_Find는 루트 노드를 빠르게 찾기 위해서 사용했다.

루트노드에서 dfs 탐색을 실행한 후 leaf노드에서 다시 한 번 dfs탐색을 실행했다.