[백준-1967] 트리의 지름

이 문제는 백준의 골드 4 레벨인 트리의 지름이라는 문제이다.

 

 

이 문제는 처음에 딱 보자마자 가장 긴 점을 어떻게 찾지..? 라는 생각이 들었다.

가중치가 없으면 찾을 수 있을 것 같은데, 가중치를 생각하니까 뭔가 더 어렵게 느껴졌다.

막연하게 dfs로 풀면 될 것 같은데... 라는 생각만 하고 있었는데, 같이 스터디 하는 친구가 로직을 알려주었다.

 

일단 이 문제는 다른 dfs 문제랑 크게 다르지 않다. 하지만 다른 점이 있다면, dfs를 두번 돌려준다는 것이다.

큰 로직을 보자면, 

1) 처음 점을 시작으로 dfs를 돌려준다

2) maxNode를 시작으로 dfs를 돌려준다. 

이게 다였다. 

 

maxNode는 dfs를 돌려줄 때 가장 dist가 max값보다 크다면 담아주었다.

코드가 길지 않으니 전체 코드!

 

import java.util.ArrayList;
import java.util.Scanner;

public class 트리의지름_1967 {
	static int N;
	static ArrayList<Node>[] list;
	static boolean[] visited;
	static int max = 0;
	static int maxNode = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		list = new ArrayList[N+1];
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<Node>();
		}
		
		for(int i=0; i<N-1; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int d = sc.nextInt();
			
			list[a].add(new Node(b,d));
			list[b].add(new Node(a,d));
		}
		
		visited = new boolean[N+1];
		visited[1] = true;
		dfs(1,0);
		
		visited = new boolean[N+1];
		visited[maxNode] = true;
		dfs(maxNode,0);
		
		System.out.println(max);
		
		
	}
	
	static void dfs(int idx, int dist) {
		for(Node n: list[idx]) {
			if(!visited[n.idx]) {
				visited[n.idx] = true;
				dfs(n.idx, dist+n.cnt);
			}
		}
		
		if(max< dist) {
			max = dist; 
			maxNode = idx;
		}
	}
	
	static class Node{
		int idx;
		int cnt;
		Node(int idx, int cnt){
			this.idx = idx;
			this.cnt = cnt;
		}
	}
}