[백준 알고리즘] 1967번 자바(Java) 트리의 지름

문제

조건

입력

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

풀이

시간복잡도 면에서 주어진 값은 최대 만이고 이중반복문을 돌려도 1억번이라 2초안에 들어온다

그렇기에 O(n^2)방법이 가능하다. 웬만한 방법은 다 되는거다.

문제는 메모리가 128MB인데 이것이 의미하는것은 이단배열이 사용이 불가능하다.
int[] arr = new int[10000][100000]; 는 4byte*10000*10000 = 400MB이기 때문이다. 
그렇다면 각 노드의 연결상태와 가중치를 어떻게 저장할것인가. 
처음에는 두가지 키를 가진 HashMap도 고민을 해봤지만 자주 쓰는경우가 없고 Java자체적으로는

함수가 없다.

중간에 한가지 헷갈렸던 부분이 이진트리인줄알고 arr[n][2] 로해서 arr[n][0]과 arr[n][1]에 좌우노드를 
넣는식으로 진행을 했는데 당연하게도 이진트리가 아니어서 틀렸다.

아무쪼록 결국 생각해낸게 자식노드의 번호를 가진 배열리스트를 만들기로 했다. 근데 이제 가중치도

저장해야하기에 자식번호와 가중치를 가진 node 클래스를 만들었다. 

그리고 그것을 각 부모 노드가 저장된 리스트에 저장하는 식으로 했다. 

 

그렇게 해서 구현한 DFS는 모든 n을 돌릴필요없이 1만 돌리면 모든 노드들을 한번씩만 방문하는
DFS가 된다. 따라서 총 시간복잡도는 O(n)이다. 

과정은 아래 그림과 같다.

1에서 시작

1->2->4->7 로 이동

7->8로 이동후 7과 8의 가중치를 비교하여 4넘버의 map[4][0]을 채우고 가중치의 합으로 map[4][1]을 채운다.

 간단한 계산을 설명하면 4에서 연결된 노드중 가중치가 가장 큰 값을 받아온다. 근데 이부분에 대해서는 
 우측 부분인 3밑에 트리를 돌면 더 이해가 쉬울거같아서 그때 자세히 설명하겠다.
 같은 식으로 2에는 4의 더 큰 가중치인 map[4][0]과 2->4의 가중치니 5을 더하여 12가 map[2][0]이 된다.

1의 노드중 2 방향으로 가는 깊이 우선탐색은 끝났으니 이제는 3으로 간다 3->5->9

9->10->6->11 이동

12까지 이동후 더큰 가중치와 가중치의 합을 채워넣으면 다음과같다

5같은 경우는 좌우중 9번이 15로 더 크므로 map[5][0] = 15, 합은 map[5][1] = 15+4 = 19

6같은 경우는 좌우중 12번이 가중치 더 크므로 map[6][0] = 10, 합은 map[6][1] = 6+11 = 16

3같은 경우는 좌우로 받는 값이 5번에서는 map[5][0] + 11 = 26, 6번에서는 map[6][0]+9 = 19 가 넘어오므로
map[3][0] = 26, 합은 map[3][1] = 26+19 = 45가 된다.

1번원의 지름보다 3번 원의 지름이 더 크다 (43<45)

따라서 제일 큰 지름은 45인것을 알 수 있다.

 

예제 입력 예시

12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10

 

예제 입력 예시

45

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//1967번
//4byte*1만*1만은 100MB -> 2단 배열 불가
//이진트리아님 가중치랑 저장노드 배열로 만들어야함
//다른문제 생김 배열리스트로 만들면 메모리초과남 -> 배열리스트를 만드는데 node형 배열리스트, 근데 이제 node안에는
//child, 가중치가 들어가야함 그래서 이제 그 new Node(child, 가중치)를 list[i].add(new Node) 해줘야함
//방문체크해야함 list[i]를 통해서 찾은 node와 node의 child 방문체크를 해야 중복해서 방문안함

public class Main {
    static ArrayList<Node>[] list;
    static int[][] map;  //0에는 연결된 노드중 가장 큰 지름, 1에는 인덱스기준 트리의 지름

    static class Node {
        int child;   //연결된 자식노드
        int weight;    //자식노드와의 가중치

        public Node(int child, int weight) {
            this.child = child;
            this.weight = weight;
        }
    }

    static int longLen;  //제일 긴 지름

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        map = new int[n + 1][2];
        list = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }

        //n-1개의 간선 입력받기
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int len = Integer.parseInt(st.nextToken());
            list[from].add(new Node(to, len));
        }

        dfs(1);
        //map[1]중 제일큰값 구하기
        for (int i = 1; i < n + 1; i++) {
            if (map[i][1] > longLen) longLen = map[i][1];
        }
        System.out.println(longLen);
    }

    static void dfs(int curIndex) {
        // System.out.print(curIndex+"->"); //트리 알맞게 순회하는지 확인
        int fiLen = 0;  //노드랑 연결된 제일긴가중치
        int seLen = 0;   //노드랑 연결된 두번째로 긴 가중치
        if (list[curIndex].size() == 0) return;
        else if (list[curIndex].size() == 1) {
            int nextIndex = list[curIndex].get(0).child;
            dfs(nextIndex);
            fiLen = map[nextIndex][0] + list[curIndex].get(0).weight; //가중치와 쌓인가중치 더하기
        } else {
            for (Node node : list[curIndex]) {
                int nextIndex = node.child;
                dfs(nextIndex);
                //자식 노드 쌓인가중치와 현재노드와 자식노드의 가중치 더하기
                int curLen = map[nextIndex][0] + node.weight;
                if (curLen > fiLen) {
                    seLen = fiLen;
                    fiLen = curLen;
                } else if (curLen > seLen) {
                    seLen = curLen;
                }
            }
        }
        //공통된 부분
        map[curIndex][0] = fiLen;
        map[curIndex][1] = fiLen + seLen;
    }
}

 

 

문제 출처

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

1967번: 트리의 지름