[백준] 1167 : 트리의 지름 JAVA 풀이

 

11725번 트리의 지름 문제에서 입력방식만 달라진 문제였다.

 

import java.io.*;
import java.util.*;

public class Main {

	static class Node{
		int idx;
		int cnt;
		Node(int idx, int cnt){
			this.idx = idx;
			this.cnt = cnt;
		}
	}
    // 정점의 개수
	static int v;
    // 최대인 거리
	static int max = 0;
    // 루트노드에서 가장 멀리 떨어진 정점
	static int max_idx = 0;
    
    // 정점을 방문했는지 검사하는 배열
	static boolean[] visit;
    // 트리를 저장할 노드들의 어레이리스트 배열을 생성
	static ArrayList<Node>[] list;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        // 정점의 개수를 입력받음
        v = Integer.parseInt(br.readLine());
		
        // 정점의 개수+1 크기의 어레이리스트 배열 생성
		list = new ArrayList[v+1];
		
        // v+1크기의 배열에 어레이리스트 공간을 할당
		for(int i=0;i<=v;i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0;i<v;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			// 정점번호
			int n = Integer.parseInt(st.nextToken());
			int tmp;
            
            // 양방향리스트를 생성
			while((tmp=Integer.parseInt(st.nextToken()))!=-1) {
				int weight=Integer.parseInt(st.nextToken());
				list[n].add(new Node(tmp, weight));
				list[tmp].add(new Node(n, weight));
			}
		}
		
        // 루트에서 가장 먼 정점을 찾기 위한 과정
        // 루트노드인 1을 방문했다고 표시 후 dfs함
		visit = new boolean[v+1];
		visit[1] = true;
		dfs(1,0);
		
        // 방문배열 초기화
        // 루트에서 가장 먼 정점에서 다시 bfs를 해 최대 거리를 구함
		visit = new boolean[v+1];
		visit[max_idx] = true;
		dfs(max_idx, 0);
		System.out.println(max);
		
	}
	
	static void dfs(int idx, int cnt) {
    	// 새로 구한 거리 == cnt가 기존 최대거리보다 더 크다면 갱신
		if(max<cnt) {
			max = cnt;
			max_idx = idx;
		}
		
        // idx 노드의 인접 정점들에 대해 dfs를 수행함
        // 수행할 때마다 거리는 업데이트해줌
		for(Node node : list[idx]) {
			if(!visit[node.idx]) {
				visit[node.idx] = true;
				dfs(node.idx, cnt+node.cnt);
			}
		}
		
		
	}

}