백준 1967 - 트리의 지름

Java

1967 번 - 트리의 지름

문제

접근 방법

우선 트리를 그래프로 연결하듯이 노드끼리 List를 통해 연결한다.

1. DFS를 통해 root 노드에서 leaf 노드 중, 도달 할 때까지 가중치가 가장 큰 노드를 구한다.
2. 그리고 그 노드를 root로 시작하여 left 까지 다시 가중치가 가장 큰 노드를 구한다.

2번 과정에서 나온 가중치가 트리의 지름이다.

코드

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

public class Main {
	static int n, result, max, deep;
	static List<List<Node>> node;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	n = stoi(br.readLine());
    	StringTokenizer stk;

    	node = new ArrayList<>();

    	for(int i = 0; i <= n; i++) {
    		node.add(new ArrayList<Node>());
    	}

    	int a,b,c;
		for(int i = 0; i < n - 1; i++) {
			stk = new StringTokenizer(br.readLine());
			a = stoi(stk.nextToken());
			b = stoi(stk.nextToken());
			c = stoi(stk.nextToken());

			node.get(a).add(new Node(b,c));
			node.get(b).add(new Node(a,c));
		}
		// 루트 노드, 이전 노드, 현재까지의 합
		DFS(1, -1, 0);
		max = 0;
		DFS(deep, -1, 0);

		System.out.println(max);
    	br.close();
	}

	static void DFS(int curN, int preV, int sum) {

		if(max < sum) {
			max = sum;
			deep = curN;
		}

		int size = node.get(curN).size();
		for(int i = 0; i < size; i++) {
			if(node.get(curN).get(i).getName() != preV) {
				DFS(node.get(curN).get(i).getName(), curN, sum + node.get(curN).get(i).getVal());
			}
		}

	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }

	static class Node{
		private int name;
		private int val;

		Node(int name, int val){
			this.name = name;
			this.val = val;
		}
		public int getName() {
			return name;
		}
		public int getVal() {
			return val;
		}
	}
}

총평

후기

개선할 점