BOJ(백준 온라인 저지) 1167번 with 자바[JAVA]

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

---

아.. 어렵다

 

처음 생각으로는 DFS 를 여러번 수행해서 각 노드에 대한 최대 길이를 구하려고 했지만

N = 100,000 이고 DFS 를 각 노드에 대해 수행하면 빨라야 O(N^2) 이기 때문에 당연히 시간초과가 발생하는거였다.

(* 10,000,000,000 번의 계산이 필요한데 일반적인 CPU 는 1억번의 연산 당 1초가 걸리기 때문에 100초가 걸린다.)

 

어쩔 수 없이 구글링을 해봤는데

단 두 번의 DFS 만으로 트리의 지름을 알 수 있는 방법이 존재했다.

 

트리의 성질을 이용하면 가능한데,

 

자세한 증명은 아래 접은 글에 첨부해놓았다.

https://velog.io/@besyia0k0/Algorithm-diameter-of-tree

[알고리즘 / 백준] 트리의 지름 알아보기 (BOJ 1967/ BOJ 1167)

 

따라서 DFS 를 두 번 만 수행한다면 트리의 지름을 2N 에 구할 수 있다.

 

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

public class Main {

    public static Node[] nodes;
    public static boolean[] visited;
    public static int vertex1Key;
    public static int N;
    public static int max = 0;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N is # of Node
        N = Integer.parseInt(br.readLine());

        nodes = new Node[N+1];

        for(int i=0; i<N; i++){

            StringTokenizer st = new StringTokenizer(br.readLine());

            int nodeKey = Integer.parseInt(st.nextToken());
            nodes[nodeKey] = new Node(nodeKey);

            int adjNodeKey = Integer.parseInt(st.nextToken());

            while(adjNodeKey != -1){

                int w = Integer.parseInt(st.nextToken());

                Node adjNode = new Node(adjNodeKey);
                adjNode.cost = w;
                nodes[nodeKey].add(adjNode);

                adjNodeKey = Integer.parseInt(st.nextToken());
            }
        }

        visited = new boolean[N+1];
        DFS(nodes[1], 0);

        visited = new boolean[N+1];
        DFS(nodes[vertex1Key], 0);

        System.out.println(max);
    }

    private static void DFS(Node start, int dist) {

        visited[start.key] = true;
        for(Node n : start.adj){
            if(!visited[n.key])
                DFS(nodes[n.key], dist + n.cost);
        }

        if(dist > max) {
            max = dist;
            vertex1Key = start.key;
        }
    }
}

class Node {
    public int key;
    public int cost;
    public ArrayList<Node> adj = new ArrayList<>();

    Node(int key){
        this.key = key;
    }

    public void add(Node n){
        adj.add(n);
    }
}

 

---

• 배운 점

트리의 지름에 대한 성질을 알게되었다. 해당 자료구조의 성질을 아는 것도 필요해보인다,