[백준] 1967번 트리의 지름(java)

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

1967번: 트리의 지름

핵심

DFS를 사용하여 풀 수 있다.

실제 부모와 자식관계의 트리이지만 양방향 매핑을 하는 인접 리스트로 표현하였다.

 

 

정답 코드 

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


public class Main {
    static int N;
    static List<Node> nodes[];
    static boolean[] visited;
    static int max;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nodes = new ArrayList[N+1];
        for(int i = 1; i <= N; i++)nodes[i] = new ArrayList<>();

        for(int i = 1; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            nodes[from].add(new Node(to,value));
            nodes[to].add(new Node(from,value));
        }

        for(int i = 1; i <= N; i++){
            visited = new boolean[N+1];
            visited[i] = true;
            dfs(i,0);
        }
        System.out.println(max);
    }

    public static void dfs(int num, int value){
        for(Node node : nodes[num]){
            if(!visited[node.link]){
                visited[node.link] = true;
                dfs(node.link, value + node.value);
            }
        }
        max = Math.max(max,value);
    }
}

class Node{
    public int link;
    public int value;

    public Node(int link, int value){
        this.link = link;
        this.value =value;
    }
}

해설

간선의 가중치, 연결된 노드 번호를 표현하기 위해 Node클래스를 만들었다.

visited를 각 실행마다 초기화해주어야 한다.

최댓값을 최대 깊이까지 탐색할 때마다 갱신해 준다.

 

 

배운 점

처음에 풀 때는 dfs를 사용하지 않고, 공통조상을 찾고, 그때 자식 노드에서 올라온 값 중 최댓값 2개를 가지고

지름을 구하는 방법을 선택했다. 하지만 노드가 1~N번이 차례대로 부모, 자식관계가 아니므로 바로 반례가 생겼다.

결국 정석대로 dfs를 사용하였다. 오히려 dfs를 사용하니 직관적이고 쉬운 것 같다.

또한 Scanner를 사용하니 시간초과가 나왔었다. 

다량의 데이터가 들어오기 때문에 BufferedReader를 사용하니 시간이 단축되어 통과할 수 있었다.

다량의 데이터가 입력으로 들어올 경우 버퍼리더를 사용하는 습관을 들이자.