[lv3] 등대

https://school.programmers.co.kr/learn/courses/30/lessons/133500#

 

트리 그래프에서의 최소 지배 집합(minimum vertex cover)을 구하는 문제라고 한다. dfs + dp를 통해 구현했다.

 

 

1. dp 점화식 세우기

 

dp[node][1] = 현재 node가 on인 경우 최솟값

= sum(child node가 root고 off인 모든 서브트리의 최솟값)

= sum(dp[child][0])

 

dp[node][0] = 현재 node가 off인 경우 최솟값

= sum( min(child node가 root고 off인 서브트리의 최솟값 , child node가 root고 on인 서브트리의 최솟값 ) ) + 현재 node를 on하는 값

= sum( min(dp[child][0] , dp[child][1]) ) + 1

 

2. dfs

 

노드 중 아무거나 root로 잡고 bottom-up 방식으로 리프노드부터 갱신한다.

최종적으로 전체 트리를 이루는 최솟값을 구하고, on/off인 경우 중 min을 반환한다.

 

 

import java.util.*;

class Solution {
    int[][] dp;
    List<Integer>[] adj;

    // DFS로 트리를 탐색하며 최소 지배 집합 계산
    void solve(int node, int parent) {

        dp[node][0] = 0; // node를 끄는 값
        dp[node][1] = 1; // node를 켜는 값

        for (int neighbor : adj[node]) {
            // 부모 노드는 집계에서 제외
            if (neighbor == parent) continue;

            solve(neighbor, node); // 자식 노드 탐색

            // node를 끈다면, 자식은 반드시 켜져야 함
            dp[node][0] += dp[neighbor][1];

            // node를 켠다면, 자식은 켜거나 꺼질 수 있음
            dp[node][1] += Math.min(dp[neighbor][0], dp[neighbor][1]);
        }
    }

    public int solution(int n, int[][] lighthouse) {
        dp = new int[n + 1][2];
        adj = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int[] edge : lighthouse) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        solve(1, -1); // 1을 root로 시작 (아무 노드나 가능)

        return Math.min(dp[1][0], dp[1][1]);
    }
}