[백준-1167] 트리의 지름

이 문제는 백준 골드 3 레벨 문제이다. 

 

 

바로 전에 썼던 1967 트리의 지름이랑 정말 비슷한 문제인데, 거의 같다고 봐도 무방하다.

입력이 조금 달라서, 한 단계 높게 측정된 것 같다.

1) N이 입력 되고, 

2) 정점 하나가 나온다. 

3) 그 정점에 연결된 노드와 가중치가 쭉 나오다가 -1이 나오면 다음 정점으로 넘어가는 형식의 입력을 가졌다.

 

2와 3이 N번 반복되면 입력이 끝난다. 

이 처리를 잘 해 주는 것이 이 문제의 관건이었는데, 나는 while문을 사용해서 해결했다.

package 그래프;

import java.util.LinkedList;
import java.util.Scanner;


public class 트리의지름_1167 {
	static int N;
	static LinkedList<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 LinkedList[N+1];
		
		for (int i=0; i<N+1; i++) {
			list[i] = new LinkedList<Node>();
		}
		
		int a = 0;
		int b = 0;
		for(int i=1; i<=N; i++) {
			int n = sc.nextInt();
			while(a != -1) {
				a = sc.nextInt();
				if(a != -1) {
					b = sc.nextInt();
					
					list[n].add(new Node(a,b));
					list[a].add(new Node(n,b));
				}
			}
			a=0;
			b=0;
		}
		
		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 dist){
			this.idx = idx;
			this.cnt = dist;
		}
	}
}