[Algorithm] 백준 트리 DP문제 - 트리의 독립집합(2213) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 트리의 독립집합 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2213

2213번: 트리의 독립집합

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        Graph graph = new Graph(n);
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) graph.addWeight(i, parseInt(st.nextToken()));
        
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            graph.addEdge(parseInt(st.nextToken()), parseInt(st.nextToken()));
        }

        graph.run();
    }    
}

class Graph {
    int n;
    Node[] nodes; // 노드 배열
    Queue<Node> queue = new PriorityQueue<>(Comparator.comparing((Node n) -> n.x)); // 독립 집합
    int[] dp, arr, selected; // dp, arr(집합의 가중치), 선택된 배열
    
    Graph (int n) {
        this.n = n;
        nodes = new Node[n + 1]; // 노드 배열
        dp = new int[n + 1];
        arr = new int[n + 1];
        selected = new int[n + 1];
        
        for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
    }
    
    class Node {
        int x; // 노드 번호
        List<Node> adjacent = new ArrayList<>(); // 인접 노드
        List<Node> tree = new ArrayList<>(); // 트리
        Node (int x) {
            this.x = x;
        }
    }
    
    void addWeight (int x, int w) {
        arr[x] = w;
    }
    
    void addEdge(int x, int y) {  // 양뱡향 연관 관계
        Node n1 = nodes[x];
        Node n2 = nodes[y];
        
        n1.adjacent.add(n2);
        n2.adjacent.add(n1);
    }
    
    void run() {
        buildTree(nodes[1], nodes[0]);

        StringBuilder sb = new StringBuilder();
        int t1 = dp(nodes[1], 0); // 루트 포함 X
        int t2 = dp(nodes[1], 1); // 루트 포함
        
        if (t1 < t2) selected[1] = 1; // 만약 포함이 더 크다면 1
        else selected[1] = 0; // 아니라면 0
        sb.append(Math.max(t1, t2)).append("\n");
        
        trace(nodes[1], selected[1]); // 1번 노드에 대한 선택 여부로 추적
        
        while(!queue.isEmpty()) {
            sb.append(queue.poll().x).append(" "); // 큐의 노드 번호를 sb에 추가
        }

        System.out.println(sb);
    }

    void buildTree(Node now, Node parent) { // 트리 만들기, 현재 노드, 부모 노드
        for (Node child : now.adjacent) { // 현재 노드의 인접 노드
            if (child != parent) { // 부모 노드라면 무한 루프이므로 제거
                now.tree.add(child); // 트리에 추가
                buildTree(child, now); // 재귀 호출
            }
        }
    }
    
    int dp(Node now, int include) {
        int ans = 0;

        if (include == 1) {
            for (Node next : now.tree) ans += dp(next, 0); // 다음 노드는 포함하지 않음
            return ans + arr[now.x];
        } else {
            for (Node next : now.tree) {
                int t1 = dp(next, 0); // 현재 포함 안한 경우 다음에도 포함 안할 수 있음
                int t2 = dp(next, 1); // 다음은 포함하도록 
                
                if (t1 < t2) selected[next.x] = 1; // 포함이 더크면 포함 처리
                else selected[next.x] = 0; // 미포함 처리
                ans += Math.max(t1, t2);
            }
            return ans;
        }
    }
    
    void trace(Node now, int include) {
        if (include == 1) { // 현재를 포함했다면
            queue.add(now); // 큐에 추가하기
            for (Node next : now.tree) trace(next, 0); // 다음은 무조건 불가
        }
        else if (include == 0) {
            for (Node next : now.tree) trace(next, selected[next.x]); // 다음은 dp의 더 큰 값에 따라 달라짐
        }
    }
}

 

2. 풀이 중점 사항 

 

독립 집합은 그래프 이론에서 어떤 두 꼭짓점도 서로 인접하지 않는 그래프에 있는 꼭짓점들의 집합을 의미합니다. 이는 곳 간선으로 직접적으로 인접해 있지 않은 노드들을 의미합니다. 트리의 독립집합을 구하는 알고리즘은 일반적인 그래프에서 NP - 하드 문제로 알려져 있습니다.

 

이 문제를 해결하기 위해, 트리 구조, DP, 재귀의 방식이 사용 되었습니다.

저는 한 번에 해결하지 못하여, 하단의 블로그를 참고하였습니다.

 

주요 소스는 다음과 같습니다.

 

트리 

 

void buildTree(Node now, Node parent) { // 트리 만들기, 현재 노드, 부모 노드
    for (Node child : now.adjacent) { // 현재 노드의 인접 노드
        if (child != parent) { // 부모 노드라면 무한 루프이므로 제거
            now.tree.add(child); // 트리에 추가
            buildTree(child, now); // 재귀 호출
        }
    }
}

 

인접한 노드들 간에 트리 구조를 형성하기 위해 buildTree를 토대로 현재 노드, 부모 노드를 인자로 받았습니다.

만약 현재 노드의 인접한 노드 중 부모 노드가 다시 tree로 설정된다면 무한 루프에 빠질 수 있습니다. 따라서, 부모 노드를 제외하고 트리를 추가한 후 재귀로 호출하였습니다.

 

dp 

 

int dp(Node now, int include) {
    int ans = 0;

    if (include == 1) {
        for (Node next : now.tree) ans += dp(next, 0); // 다음 노드는 포함하지 않음
        return ans + arr[now.x];
    } else {
        for (Node next : now.tree) {
            int t1 = dp(next, 0); // 현재 포함 안한 경우 다음에도 포함 안할 수 있음
            int t2 = dp(next, 1); // 다음은 포함하도록 
            
            if (t1 < t2) selected[next.x] = 1; // 포함이 더크면 포함 처리
            else selected[next.x] = 0; // 미포함 처리
            ans += Math.max(t1, t2);
        }
        return ans;
    }
}

 

특정 스티커를 선택해야 할 때, 인접한 스티커를 선택하지 못하는 DP 문제가 있습니다. 이 소스도 그러한 원리와 비슷하다고 볼 수 있습니다. include는 현재 선택된 노드인지를 알려주는 지표로, 만약 선택했다면 다음 노드는 선택할 수 없습니다.

 

반면 현재 선택되지 않았다면, 다음에도 역시 선택 안 할 수 있고 선택할 수도 있습니다.

예를 들어 [1, 100, 10, 5, 200]이 있다면, 인접하지 않게 골라야 할 때, 100을 골랐다고 해서 반드시 10을 고를 필요는 없는 것과 동일합니다. 따라서, 두 가지 경우를 파악한 후 더 큰 곳에 포함 처리하도록 하였습니다.

 

 

이상으로 백준 트리의 독립 집합 자바 풀이를 마치도록 하겠습니다.

감사합니다!!!