백준 No.1967 트리의 지름- JAVA

문제

트리는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트라의 지름은 45가 된다.

 

풀이 

해당 문제를 조금 다르게 보면 9번 노드에서 12번 노드로 향하는 가중치가 45이다. 그렇게 접근하니 바로 풀렸다.

모든 노드들에서 한번씩 dfs 탐색을 하면서 가중치를 더하면서 큰 값을 계속 저장해나간다. 이러면서 값이 바뀌는 경우가 있을 것이고 안 바뀌는 경우도 있을 것이다. 이러면서 결국 제일 큰값 45가 solution변수에 들어가게 된다. 

핵심코드

static void dfs(int index, int cost){
	visited[index] = true;
    for(Node node : graph.get(index)){
    	if(!visited[node.edge]){
        	dfs(nodex.edge, cost+ node.cost);
        }
     }
     solution = Math.max(solition,cost);
  }

 

 

전체 코드

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

public class Main {


    static ArrayList<ArrayList<Node>> list = new ArrayList<>();
    static boolean visited[];
    static int N;

    static int solution = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());



        for (int i = 0; i < N+1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < N-1 ; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            list.get(start).add(new Node(end,cost));
            list.get(end).add(new Node(start,cost));
        }

        for (int i = 1; i <= N; i++) {
            visited = new boolean[N+1];
            dfs(i,0);
        }

        System.out.println(solution);
    }
    static void dfs(int index, int cost){
        visited[index] = true;

        for(Node node : list.get(index)){
            if(!visited[node.edge]){
                dfs(node.edge,cost + node.cost);
            }
        }

        solution = Math.max(solution,cost);
    }



    static class Node{
        int edge;
        int cost;

        public Node(int edge,int cost){
            this.edge = edge;
            this.cost = cost;
        }
    }
}