[BOJ] 14657 준오는 최종인재야!!

문제 요약

문제 링크: 백준 14657 - 준오는 최종인재야!!

문제 설명

---

접근 방법

트리의 지름을 구하는 방법으로 접근했다. 원래 트리의 지름은 간선의 가중치가 가장 긴 것으로 지름의 끝 점을 구하지만, 이 문제에선 연결된 노드가 가장 많고, 가중치는 짧은 노드를 골라야 했다. dfs를 통해 임의의 정점(1)에서 start_n (지름의 끝 점)을 구해준다.

지름의 끝 점을 구한 후, 한번 더 dfs를 통해 지름의 끝 점에서 부터 모든 정점까지의 노드 개수와 거리를 구해준 후, 연결된 노드가 가장 많고, 가중치가 짧은 노드를 정답 처리에 활용한다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, t, max_d, min_cost = 1e9;
pair<int, int> dis[50001];
vector<pair<int, int>>v[50001];

void dfs(int x, int d, int cost) {
    for (auto i : v[x]) {
        if (dis[i.first].first == -1) {
            dis[i.first].first = d + 1;
            dis[i.first].second = cost + i.second;
            dfs(i.first, d + 1, cost + i.second);
        }
    }
}

void init() {
    for (int i = 1; i <= n; i++) {
        dis[i].first = -1;
        dis[i].second = 1e9;
    }
}

void solve() {
    init();
    dis[1] = { 0, 0 };
    dfs(1, 0, 0);
    int mx_d = 0, mn_cost = 1e9, start_n = 0;
    for (int i = 2; i <= n; i++) {
        if (mx_d < dis[i].first) {
            mx_d = dis[i].first;
            mn_cost = dis[i].second;
            start_n = i;
        }
        else if (mx_d == dis[i].first && mn_cost > dis[i].second) {
            mn_cost = dis[i].second;
            start_n = i;
        }
    }
   	// start_n이 트리의 지름에서 한 끝 점

    init();
    dis[start_n].first = 0;
    dfs(start_n, 0, 0);
    for (int i = 1; i <= n; i++) {
        // 문제를 많이 풀되 짧은 시간
        if (dis[i].first > max_d) {
            max_d = dis[i].first;
            min_cost = dis[i].second;
        }
        else if (dis[i].first == max_d)
            min_cost = min(min_cost, dis[i].second);
    }
    int ans = min_cost / t;
    if (min_cost % t != 0) ans++;
    cout << ans;
}

void input() {
    cin >> n >> t;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}

---

마무리

트리의 지름 응용 문제