백준 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<int[]> 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);
	}
}

 

똑같은 문제로 "백준 1167_트리의 지름"이 있습니다.