BOJ 1967번 트리의 지름

BOJ : https://www.acmicpc.net/problem/1967

github : https://github.com/junho0956/Algorithm/blob/master/1967/1967/%EC%86%8C%EC%8A%A4.cpp

 

처음에는 트리의 지름이라는 것을 단순히 리프노드 사이끼리의 최장거리 로만 생각했다.

그래서 풀어낸 코드는 리프노드일 경우 다른 리프노드를 찾아가는 dfs 를 했고

채점결과를 보니 정답은 받았지만 시간이 다른정답자에 비해 길다는 것을 알았다.

솔직히 문제를 풀면서 시간이 오래걸릴 것 같기는 했다.

각 리프노드마다 전체를 다 방문해야되니 O(N^2) 의 시간이 필요해서이다.

근데 이걸 어떻게 시간을 줄일 수 있는 걸까 고민을 해보았는데

트리의 지름이라는 것을 이해하게 되니 더욱 쉬워졌다.

 

트리의 지름이라는게 결국 가장 긴 리프노드 사이의 값이 되고 지름을 위한 노드가 2개가 명확히 결정된다.

그럼 임의의 리프노드에서 처음에 탐색을 마치게 되면

임의의 리프노드가 지름을 이루는 노드 중 1개가 아니더라도

최장거리를 반환하기 위한 노드는 지름을 이루는 2개의 노드 중 1개가 된다는 것이다.

 

결국 1번의 탐색으로 지름 중 1개의 노드를 찾을 수 있게 되는 것이다.

그럼 이 노드를 이용해서 다시 한번 전체를 탐색해주면 나머지 찾지 못한 노드를 찾을 수 있게 되는 것이다.

이해가 안된다면 .. 다시 한번 읽어보자

 

BOJ 1167번 문제가 같은 트리의 지름인데 노드가 10배가 많으니 현재 코드로는 시간초과가 당연할 수 밖에 없다.

위에서 설명한 2번의 dfs 를 이용하는 코드는 BOJ 1167번을 풀면서 다시 한번 설명하겠다.

BOJ 1167번 : 트리의 지름 https://junho0956.tistory.com/122?category=825559

 

아래 코드는 단순히 1967 번을 푸는데 문제는 없으므로 단순 이해를 위해 도움이 되었으면 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool visit[10001];
vector<pair<int, int> > v[10001];
int N, f, s, w;
 
int dfs(int now) {
    if (visit[now]) return 0;
    visit[now] = 1;
 
    int total = 0;
    for (int i = 0; i < v[now].size(); i++) {
        if (visit[v[now][i].first] == 0) {
            total = max(total, dfs(v[now][i].first) + v[now][i].second);
        }
    }
 
    return total;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        cin >> f >> s >> w;
        v[f].push_back({ s,w });
        v[s].push_back({ f,w });
    }
 
    int Max = 0;
    for (int i = 1; i <= N; i++) {
        if (v[i].size() == 1) {
            int len = dfs(i);
            Max = Max < len ? len : Max;
            for (int i = 1; i <= N; i++) visit[i] = 0;
        }
    }
 
    cout << Max;
    return 0;
}