[Java] 백준 1967번 - 트리의 지름

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

1967번: 트리의 지름

 

[ 1 ] 풀이 및 소스코드

- 트리의 지름은 모든 노드에 대해 DFS를 하여 트리에 존재하는 모든 경로 중 가장 긴 것(가중치가 큰 경로)을 찾음으로써 구할 수 있다.

- 각 노드마다 DFS를 통해 연결된 노드들의 가중치를 더해가며 distance를 구하고, max를 업데이트 해 준다.

- 모든 노드에 대해 DFS를 실행한 후의 max 값이 트리의 지름이 된다.

- 각 노드와 간선 정보는 양방향 인접리스트에 저장했다.

- 간선에 가중치가 있기 때문에 Node 라는 클래스를 선언하여 인접리스트에 노드 정보와 간선의 가중치를 저장했다.

 

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

class Node {

    int n;
    int w;

    Node(int n, int w) {
        this.n = n;
        this.w = w;
    }

}

public class BOJ_1967 {

    static ArrayList<Node>[] list;
    static boolean[] visited;
    static int max = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        list = new ArrayList[n+1];
        for(int i = 1; i < n+1; i++) {
            list[i] = new ArrayList<Node>();
        }
        visited = new boolean[n+1];

        for(int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list[s].add(new Node(e, w));
            list[e].add(new Node(s, w));
        }

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

        System.out.println(max);

    }

    static void dfs(int s, int distance) {
        if(visited[s]) {
            return;
        }
        visited[s] = true;
        for(Node n : list[s]) {
            if(!visited[n.n]) {
                if(max < distance + n.w) {
                    max = distance + n.w;
                }
                dfs(n.n, distance + n.w);
            }
        }
    }

}

 

 

[ 2 ] 주의점

- dfs 메서드 내부에서 매개변수인 distance를 초기화하면 안 된다. 정상적인 재귀를 위해 distance + n.w 를 매개변수로 넘겨주자.

- 노드가 1개인 경우도 있기 때문에 max를 0으로 초기화해야 한다.