(Java) 트리의 지름 & 공간 복잡도 (feat. 백준 1167 트리의 지름)

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

 

트리에서 임의의 두 점 사이의 거리 중 가장 긴 거리를 구하는 문제다.

트리의 정점의 개수 V가 주어지고 V개의 줄에 걸쳐 간선의 정보가 주어졌다.

 

이 문제를 풀기 위해 플로이드-워셜 등의 방법을 잠시나마 생각해봤지만 100,000개의 정점을 삼중 반복문으로 돌릴 생각을 하니 안 된다는 것을 깨닫기까지 그렇게 오래걸리지 않았다.

 

결국 트리의 지름 공식을 알아야 풀 수 있는 문제였다.

트리의 지름 공식은 다음과 같다.

 

1. 임의의 점 A에서 가장 먼 지점 B를 찾는다.

2. B에서 가장 먼 지점 C를 찾는다.

3. B ~ C의 거리가 트리의 지름이다.

 

이 공식만 이용한다면 어렵지 않게 풀 수 있다.

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

public class Main {
    static class Node {
        int toNodeNum;
        int dist;
        Node(int toNodeNum, int dist) {
            this.toNodeNum = toNodeNum;
            this.dist = dist;
        }
    }

    static List<Node>[] list;
    static boolean[] flag;
    static int max, endPoint;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int V = Integer.parseInt(br.readLine());
        list = new ArrayList[V+1];
        for(int v = 1; v <= V; v++) {
            list[v] = new ArrayList<>();
        }

        for(int v = 1; v <= V; v++) {
            st = new StringTokenizer(br.readLine());
            int fromNodeNum = Integer.parseInt(st.nextToken());
            while(true) {
                int toNodeNum = Integer.parseInt(st.nextToken());
                if(toNodeNum == -1) break;
                int dist = Integer.parseInt(st.nextToken());
                list[fromNodeNum].add(new Node(toNodeNum, dist));
            }
        }

        flag = new boolean[V+1];
        max = 0;
        endPoint = -1;
        dfs(1, 0);	// 임의의 지점 1에서부터 가장 거리가 먼 지점 구하기
        
        // max 값과 endPoint 초기화
        max = 0;
        flag = new boolean[V+1];
        dfs(endPoint, 0);	// 트리의 지름 구하기
        System.out.println(max);
    }

    static void dfs(int fromNodeNum, int dist) {
        flag[fromNodeNum] = true;
        for (int i = 0; i < list[fromNodeNum].size(); i++) {
            Node toNode = list[fromNodeNum].get(i);
            if(flag[toNode.toNodeNum]) continue;

            dfs(toNode.toNodeNum, dist+toNode.dist);
        }
        if(dist > max) {
            max = dist;
            endPoint = fromNodeNum;
        }
    }
}

 

트리의 지름 공식을 처음 봤을 때는 이게 된다고? 했지만 마침내 이해할 수 있게 되어 증명을 공유하고자 한다.

 

우선 경로 (A, B)는 트리의 지름이라고 가정하자. (X, Y)는 서로 가장 멀리 떨어진 정점이고, 경로 (A, B)와 중간 M라는 정점에서 만난다고 가정해보자. 트리는 모든 정점이 연결되어 있으며 cycle을 만들면 안되므로 A, B, X, Y를 거치는 경로는 오직 M만 공통으로 지난다고 가정하는 것이다.

 

1. (X, Y)는 서로 가장 멀리 떨어진 정점이라고 했으니, (X, A)나 (X, B)보다 크다.

2. 위의 결과에서 (M, Y) > (M, A) or (M, B) 임을 알 수 있다. (따라서, M에서 가장 먼 정점은 Y이다.)

3. 이는 곧 (A, M) + (M, Y) > (A, M) + (M, B) → (A, Y) > (A, B) 이므로 모순이다.

 

루트에서 가장 거리가 먼 점이 지름 안에 없다는 것(역)이 모순이므로 루트에서 가장 거리가 먼 점이 지름 안에 있다는 것이 참이 된다. 이 점으로부터 거리가 가장 먼 정점까지의 거리는 지름이라는 것은 자명하다.

 

 

 

 

 

 

문제를 풀면서 또 하나 신경썼던 부분은 간선 정보를 담을 자료구조를 고르는 일이었다.

정점이 100,000개나 되다 보니 메모리 제한이 신경쓰였기 때문이다.

그래서 이번 기회에 공간 복잡도 구하는 법을 정리했다.

 

공간 복잡도를 구하는 방법

1. 기본형 객체

기본형	크기 (byte)
byte	1
short	2
int	4
long	8
float	4
double	8
char	2
boolean	1*

* boolean 타입의 크기는 JVM 구현에 따라 다를 수 있다. 일반적으로 1byte를 사용한다.

 

객체 하나마다 표에 나온 크기만큼의 바이트를 가진다.

배열은 그 기본형 타입의 크기만큼 곱해주면된다.

예를 들어 int[1000]이라면 int형이 4byte니까, 4,000byte가 되고, int[1000][1000]라면 4,000,000byte가 되는 것이다.

이는 배열과 리스트가 혼합되었을 때에도 2차원 배열처럼 계산된다.

 

 

2. 참조형 객체

참조형 객체는 기본형 객체보다 복잡하다.

Integer를 예시로 들면

 

(1) 객체 헤더: 일반적으로 12byte

• 8byte: mark word
• 4byte: 클래스 포인터

(2) int 값 저장: 4byte

(3) 패딩: 8byte

총 메모리 사용량: 12 +  4 + 8 = 24byte 과 같이 계산된다.

 

 

3. 클래스 객체

클래스 객체는 필드 값과 오버헤드 값으로 이루어져 있다.

오버헤드 값은 각 객체의 메타데이터를 저장하는데 사용된다.

 

객체가 다음과 같이 이루어져 있다면

class Node {
	int N;
    int M;
    Node(int N, int M) {
    	this.N = N;
        this.M = M;
    }
}

 

필드 값은 int형 2개이므로 4+4 = 8byte이다.

오버헤드 값은 JVM에 따라 다를 수 있지만 일반적으로 8byte이다.

따라서, 총 메모리 사용량 = 8byte(필드) + 8byte(오버헤드) = 16byte가 된다.

 

 

byte 변환 식

1. 바이트(B)에서 킬로바이트(KB)로 변환:
   KB = B / 1024
2. 바이트(B)에서 메가바이트(MB)로 변환:
   MB = B / (1024 * 1024)
3. 바이트(B)에서 기가바이트(GB)로 변환:
   GB = B / (1024 * 1024 * 1024)

 

 

만약 int[100000][100000]으로 선택했다면 약 40,000,000,000byte로 40GB에 달했을 것이다.

그래서 조건에는 안 적혀있지만 간선 정보가 적정한 선에서 나오리라 생각하고 배열 + List의 조합으로 작성했더니 다행히 통과할 수 있었다.