백준 1967 - 트리의지름

백준 1967 - 트리의지름

1. 유형

트리

2. 문제 분석

2-1. 문제 설명

트리에서 가장 긴 두 점은 리프 노드끼리의 거리임을 직관적으로 알 수 있습니다.

따라서 리프노드에서 재귀의 리턴 값을 사용해서 문제를 풀어야 합니다.

그림1

[그림 1]에서 지름은 9->5->3->6->12입니다. 저 케이스를 예시로 들어봅시다.

DP [k] = n => 노드 k를 기준으로 한 가장 긴 지름은 n이다.라고 정의

우선은 리프 노드까지 dfs를 진행합니다.

9에서 15를 리턴하고, 10에서 4를 리턴합니다.

노드 5에서는 15와 4중 더 긴 큰 값을 리턴합니다.

노드 3 에서는 왼쪽에서 오는 가장 큰 값 26, 오른쪽에서 오는 가장 큰 값 19를 DP [3]에 저장

2-2. 주의할 점

자식 노드가 3개 이상일 수 있습니다. 따라서 둘 중에 최댓값이 아니라, 자식 노드한테서 리턴 값을 받을 때,

2번째로 큰 수까지 구해줘야 합니다.

3. 코드

import java.io.*; import java.util.*; public class boj_1967_트리의지름 { static int N, dp[]; static List list[]; static boolean V[]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = stoi(st.nextToken()); V = new boolean[N + 1]; dp = new int[N + 1]; list = new ArrayList[N + 1]; for (int i = 0; i <= N; i++) { list[i] = new ArrayList<>(); } for (int i = 0; i < N - 1; i++) { st = new StringTokenizer(br.readLine()); int a = stoi(st.nextToken()); int b = stoi(st.nextToken()); int c = stoi(st.nextToken()); list[a].add(new int[] { b, c }); list[b].add(new int[] { a, c }); } V[1] = true; dfs(1, 0); int m = Arrays.stream(dp).max().getAsInt(); System.out.println(m); } static int dfs(int n, int w) { int maxone = 0; int maxtwo = 0; for (int next[] : list[n]) { if (!V[next[0]]) { V[next[0]] = true; int temp = dfs(next[0], next[1]); if (maxone < temp) { maxtwo = maxone; maxone = temp; } else if (maxone >= temp && maxtwo < temp) { maxtwo = temp; } } } dp[n] = maxone + maxtwo; return w + maxone; } static int stoi(String s) { return Integer.valueOf(s); } }

from http://moons-memo.tistory.com/251 by ccl(A) rewrite - 2021-09-24 21:00:44