[백준] 사회망 서비스(SNS) (tree DP) 최적화

 

[백준] 2533 - 사회망 서비스(SNS) (tree DP)

---

해결 과정 및 코드

핵심 최적화 아이디어

1. ArrayList → 배열 기반 인접 리스트: 메모리 접근 패턴 개선
   • ArrayList<Integer>[] 대신 int[] head, next, to 사용
2. 2차원 → 1차원 DP 배열: 메모리 접근 최적화
   • dp[node][0/1] 대신 dp0[node], dp1[node] 분리
3. 비트 연산 활용: 곱셈을 시프트 연산으로 대체
   • 2 * n → n << 1로 연산

---

코드

시간 복잡도: O(N)
공간 복잡도: O(N)

import java.io.*;

public class Main {
    static int[] head, next, to;           // 배열 기반 인접 리스트
    static int[] dp0, dp1;                 // 1차원 DP 배열 분리
    static boolean[] visited;
    static int edgeCount = 0;

    public static void main(String[] args) throws IOException {
        int n = read();

        // 배열 기반 인접 리스트 초기화
        head = new int[n + 1];
        for (int i = 1; i <= n; i++) head[i] = -1;  // Arrays.fill 대신 직접 루프

        next = new int[n << 1];  // 비트 시프트로 2*n 계산
        to = new int[n << 1];

        // 간선 정보 입력
        for (int i = 0; i < n - 1; i++) {
            int u = read(), v = read();
            addEdge(u, v);  // u → v 방향 간선 추가
            addEdge(v, u);  // v → u 방향 간선 추가 (무방향)
        }

        // 1차원 DP 배열로 메모리 효율성 향상
        dp0 = new int[n + 1];  // 얼리 어답터가 아닌 경우
        dp1 = new int[n + 1];  // 얼리 어답터인 경우
        visited = new boolean[n + 1];

        dfs(1);  // 1번 노드를 루트로 DFS 시작

        // 루트의 두 경우 중 최소값 출력
        System.out.println(Math.min(dp0[1], dp1[1]));
    }

    // 배열 기반 인접 리스트에 간선 추가
    static void addEdge(int u, int v) {
        to[edgeCount] = v;              // 목적지 노드 저장
        next[edgeCount] = head[u];      // 이전 간선과 연결
        head[u] = edgeCount++;          // 새 간선을 head로 설정
    }

    static void dfs(int node) {
        visited[node] = true;
        dp1[node] = 1;  // 얼리 어답터인 경우 자기 자신 포함

        // 배열 기반 인접 리스트 순회
        for (int i = head[node]; i != -1; i = next[i]) {
            int child = to[i];
            if (!visited[child]) {
                dfs(child);  // 자식 노드 먼저 계산

                // DP 점화식 적용
                dp0[node] += dp1[child];                    // 현재 노드가 얼리 어답터 아님
                dp1[node] += Math.min(dp0[child], dp1[child]); // 현재 노드가 얼리 어답터
            }
        }
    }

    // 빠른 정수 입력을 위한 read 함수
    public static int read() throws IOException {
        int cur, n = System.in.read() & 15;
        boolean isNegative = (n == 13);
        if (isNegative) n = System.in.read() & 15;
        while ((cur = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (cur & 15);  // n*10 + digit
        }
        return isNegative ? -n : n;
    }
}

 

---

최적화 분석

1. ArrayList vs 배열 기반 인접 리스트

ArrayList 방식:

ArrayList<Integer>[] adj = new ArrayList[n + 1];
for (int child : adj[node]) { ... }  // Enhanced for loop + Iterator

 

배열 기반 방식:

int[] head, next, to;
for (int i = head[node]; i != -1; i = next[i]) { ... }  // 직접 배열 접근

 

성능 차이:

• 접근 방식: ArrayList는 Integer 객체 접근, 배열은 직접 인덱스 접근
  • 간접 참조: ArrayList는 obj → array → element 단계로 접근
    1. adj[5] → ArrayList 객체에 접근
    2. .get(2) → ArrayList 내부의 배열에서 인덱스 2 찾기
    3. Integer 객체 반환
• 메모리 사용량: ArrayList는 각 노드마다 별도 동적 배열 객체, 배열은 고정 크기 int 배열 3개

2. Java 2D 배열의 메모리 구조

Java에는 진정한 다차원 배열이 없음 - int[][]는 "배열들의 배열"

메모리 레이아웃:

int[][] dp = new int[n][2];  // n+1개의 별도 배열 객체 생성

• 외부 배열: int[] 레퍼런스들을 저장하는 배열 (8-20바이트 헤더 + n×4바이트)
• 내부 배열들: 각각 별도의 int[2] 배열 (각각 8-20바이트 헤더 + 8바이트)

1차원 분리 방식:

int[] dp0 = new int[n];  // 단일 배열 (8-20바이트 헤더 + n×4바이트)
int[] dp1 = new int[n];  // 단일 배열 (8-20바이트 헤더 + n×4바이트)  

객체 헤더 구성 (64비트 JVM 기준)

• Mark Word: 8바이트 (identity hashcode, 동기화 정보, GC 메타데이터)
• Class Word: 4바이트 (Compressed OOPs 사용시) 또는 8바이트
• Array Length: 4바이트 (배열인 경우)

3. 최적화 전/후 주요 성능 차이 원인

1. ArrayList → 배열: 가장 큰 성능 향상 (객체 오버헤드 제거)
2. 2D → 1D 분리:
   접근 패턴:
   • 2D 배열: dp[i][j] → 외부 배열에서 내부 배열 참조 찾기 → 내부 배열에서 데이터 접근
   • 1D 배열: dp0[i] → 직접 배열에서 데이터 접근
   메모리 오버헤드: 2D 배열은 각 내부 배열마다 추가 객체 헤더가 필요