[백준 1167] 트리의 지름

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

1167번: 트리의 지름

 

일단 맨 처음 생각한 것은!!

리프 노드를 시작점으로 하여 dfs 탐색을 하는 거였다..

 

 

 

그리고 이 방식의 문제점..

 

노드의 개수가 최대 10만개이므로, 한 번의 dfs탐색의 시간복잡도는 대략적으로 O(n)이다..

    리프 노드의 개수만큼 dfs가 수행되어야 하므로 최종 시간복잡도는 O(n2)이며 이는 무조건 시간초과 이다......

 

 

 

 

고민하다 구글링해서 힌트를 얻었다

 

문제에서 말하는 트리의 지름이란, 두 점 사이의 거리 중 가장 긴 것 이다.

이 때 이 두 점을 다음과 같이 길게 편 형태로 생각하여 볼 수 있다.

 

 

 

이 때 저 지름에 대한 경로 길이를 구하면 된다.

그리고 지름의 두 점은 두 번의 DFS를 통하여 구할 수 있다.

지름의 두 점은 트리로 표현하였을 때 둘 다 리프 노드이며

한 쪽에 치우쳐 있는 노드를 출발점으로 하여 탐색하였을 때는 지름의 반대쪽 점까지의 거리를 최대로 구할 수 있고,

여기서 구한 점에서 출발하는 dfs 탐색으로는 반대쪽 지름의 점을 구할 수 있을 것이다..

이를 통하여 코드를 다음과 같이 작성하였다

 

 

 

주의해야 했던 점)

문제에 정점 번호 순서대로 간선 정보가 주어진다는 말이 없으므로 ㅡㅡ

정점 번호를 매 줄마다 확인해야한다.

하긴 순서대로 줄 거였으면 번호 값을 굳이 입력시켜주지 않았을 것 같다..

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static boolean[] isVisited;
    static int[][] linklist;
    static int maxValue;
    static int vertex;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.valueOf(br.readLine());
        //초기화
        isVisited = new boolean[count+1];
        linklist = new int[count + 1][];//열의 개수

        for (int i = 0; i < count; i++) {
            String line = br.readLine();
            int num = Integer.valueOf(line.split(" ")[0]);
            linklist[num] = (Arrays.stream(line.split(" "))
                    .mapToInt(Integer::parseInt).toArray());
        }

        maxValue=0;
        dfs(1, 0);
        maxValue=0;
        isVisited = new boolean[count+1];
        dfs(vertex, 0);
        bw.write(String.valueOf(maxValue));
        bw.flush();
        bw.close();
    }

    private static void dfs(int source, int sum) {
        isVisited[source] = true;
        int arr[] = linklist[source];
        int len = arr.length;
        int nextSum = sum;

        for (int i = 1; i < len - 1; i += 2) {
            int dest = arr[i];
            nextSum=sum + arr[i + 1];
            if (!isVisited[dest]) {
                if (nextSum > maxValue) {
                    maxValue = nextSum;
                    vertex = dest;
                }
                dfs(dest, nextSum);
            }
        }
    }
}

 

 

---

참고

https://velog.io/@tpclsrn7942/%EB%B0%B1%EC%A4%80-1967%EB%B2%88-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84

[백준 1967번] 트리의 지름