백준 풀이 1967 - 트리의 지름 - 그래프 탐색(DFS)

백준 풀이 1967 - 트리의 지름 - 그래프 탐색(DFS)

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

DFS를 반복하여 거리 합의 최댓값을 구하는 문제이다.

양쪽 최하위 노드까지의 거리가 지름 후보이므로, 최하위 노드들의 목록을 별도로 선언하였다.

이후 DFS를 통해 최댓값을 측정하였다.

다만, 입력과정에서 1번 노드의 자식이 하나만 있을 경우, 1번이 끄트머리 노드가 되지 않는 문제가 있었다.

다행히 1번은 항상 최상위 노드이므로, 해당 경우에 1번 노드를 끄트머리 목록에 포함시키는 것으로 해결하였다.

#include #define X first #define Y second using namespace std; int ans = 0; bool eList[10001]; bool vis[10001]; vector > graph[10001]; int start; void DFS(int idx, int d) { if (idx != start && eList[idx]) { ans = max(d, ans); return; } for (int i = 0; i < graph[idx].size(); ++i) { int a = graph[idx][i].X; int b = graph[idx][i].Y; if (vis[a]) continue; vis[a] = true; DFS(a, d + b); } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i < n - 1; ++i) { int a, b, l; cin >> a >> b >> l; eList[a] = false; eList[b] = true; graph[a].push_back({b, l}); graph[b].push_back({a, l}); } if (graph[1].size() == 1) eList[1] = true; for (int i = 1; i <= 10000; ++i) { if (!eList[i]) continue; memset(vis, false, sizeof(bool) * 10001); start = i; vis[i] = true; DFS(i, 0); } cout << ans; }

풀이 시간: 1:19:20

from http://oceanshape.tistory.com/44 by ccl(A) rewrite - 2021-08-02 00:26:22