🎄 백준 No.1967 트리의 지름

🔗 https://www.acmicpc.net/problem/1967

1. 문제

2. 입출력

• 입력 예시
  12
  1 2 3
  1 3 2
  2 4 5
  3 5 11
  3 6 9
  4 7 1
  4 8 7
  5 9 15
  5 10 4
  6 11 6
  6 12 10

• 출력 예시
  45

3. 문제 풀이

• dfs 사용
• 양방향 트리
• Node Class 생성하여 index와 가중치 저장
• isVisit으로 방문 여부 체크

4. 코드

💡 List<> x[] = new ArrayList<>();

: List의 ArrayList

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	private static boolean[] isVisit;
	private static List<Node> arrTree[];
	private static int resultDiameter;
	
	private static void dfs(int idx, int dia) {
		isVisit[idx] = true;
		for(Node node : arrTree[idx]) {
			if(isVisit[node.idx] == false) dfs(node.idx, dia + node.weight);
		}
		resultDiameter = resultDiameter > dia ? resultDiameter : dia;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		
		arrTree = new ArrayList[num + 1];
		for(int i = 1; i < num + 1; i++) {
			arrTree[i] = new ArrayList<Node>();
		}

		String[] treeInfo = new String[3];
		for(int i = 0; i < num - 1; i++) {
			treeInfo = br.readLine().split(" ");
			int parent = Integer.valueOf(treeInfo[0]);
			int child = Integer.valueOf(treeInfo[1]);
			int weight = Integer.valueOf(treeInfo[2]);
			
			arrTree[parent].add(new Node(child, weight));
			arrTree[child].add(new Node(parent, weight));
		}

		resultDiameter = 0;
		for(int i = 1; i < num+1; i++) {
			isVisit = new boolean[num + 1];
			dfs(i, 0);
		}
		
		System.out.println(resultDiameter);
	}
	
	private static class Node{
		int idx;
		int weight;
		
		private Node(int idx, int weight) {
			this.idx = idx;
			this.weight = weight;
		}
	}
}