[코드트리] 4 - 트리 DP, LCA, 한 달 공부 후기, 2차 갭체크

트리 DP

트리dp -> 트리 DP는 여러 서브트리의 최적해의 조합으로 이루어진다.

반환값이 있는 DFS는 최상위 루트 노드에서 값을 한번만 처리할 때, dp 배열을 대신해서 쓸 수 있고 

점화식의 정의를 dfs 구현으로 대체할 수 있다.

 

상태를 설계할때는 현재 노드 u가 부모 노드에게 어떤 값을 넘겨줘야 하는지를 u의 입장에서 생각해봐야 함.

-> 현재 노드가 부모에게 어떤 약속을 하는가?

-> u 기준으로 u가 누구에 의해 해결되는가?

 

LCA

LCA -> Lowest Common Ancestor, 가장 가까운 공통 조상 구하기

트리에서는 특정 정점에서 특정 정점으로 가는 경로가 유일하다. 

이 성질을 활용해서 가장 가까운 공통 조상을 구하기 위한 전처리를 미리 구해놓고 쿼리마다 적절히 연산하면

쿼리수가 많아도 N+Q log N 시간에 처리할 수 있다.

 

binary Lifting 할때 점화식은 parent[i][u] = parent[i-1][parent[i-1][u]];

-> 현재 노드 u에서 2^i 칸만큼 올라갔을 때 도달하는 노드 번호

LOG 계산할때는 while( N >= 1<<LOG) LOG++로 해주고 parent = new int [LOG][N+1]

 

구현 : Binary Lifting 및 전처리

초기화 및 depth, others 계산

1) depth dfs로 +1 해가면서 계산하고 parent[0][현재 노드] = 현재 부모 로 초기화

-> 추가 조건에 따라 초기화 추가로 들어갈 수 있음.

2) 추가 조건 (가중치, 미리 색칠된 노드 갯수 등)이 있으면 depth 계산할때 같이 함

 

Sparse Table 채우기

3) parent [1, LOG-1] [1, N] 채우기

-> 2^i 칸만큼 올라갔을 때 만나는 노드 번호 미리 계산

 

LCA 구하기

4) 만약 depth[b]가 depth[a] 보다 크다면 depth[a]가 크게 swap

 

5) diff = depth[a] - depth[b] 라 할때 

i = [LOG-1, 0] 일때 (diff & (1<<i)) != 0 이면 2진수로 나타냈을때 해당 자리가 1이니까

2^자릿수 만큼 점프해서 a와 b의 depth 똑같이 맞춤

-> a = parent[i][a]

-> 여기서 a=b면 a가 LCA

 

6) i = [LOG-1, 0] 일때 점프해서 LCA 위로 넘어가버리면 안되니까

parent[i][a] != parent[i][b] 일때 a = parent[i][a] , b = parent[i][b] 로 둘이 같이 LCA 바로 아래까지 점프함

 

7) parent[0][a] 이 LCA 

---

문제 - 트리 위에 물건 놓기

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-node-best-count/description

트리 위에 물건 놓기 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static int N;
    static ArrayList<Integer>[] g;
    static int[][] dp;
    static boolean[] visited;

    static void dfs(int ci){
        visited[ci] = true;
        dp[ci][1] = 1;

        for(int n : g[ci]){
            if(visited[n])
                continue;
            dfs(n);
            dp[ci][0] += dp[n][1];
            dp[ci][1] += Math.min(dp[n][0], dp[n][1]);
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        g = new ArrayList[N+1];
        dp = new int[N+1][2];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();
        
        for(int i = 1; i<N; i++){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }
        visited = new boolean[N+1];
        dfs(1);
        System.out.print(Math.min(dp[1][0], dp[1][1]));
    }
}

사고의 흐름

모든 간선에 대해 간선의 양끝의 두 점중 최소 하나에는 물건이 놓여야 할 때

전체 트리에서 이 조건을 만족하기 위해 필요한 최소 물건의 갯수를 구하는 문제임

상태는 현재 서브트리의 루트 노드로 두면 될 거 같다.

 

풀이

dp [ u ] [ 0 ] = 현재 노드 u를 선택하지 않았을 때, u 서브트리에서 필요한 최소 갯수

dp [ u ] [ 1 ] = 현재 노드 u를 선택했을 때, u 서브트리에서 필요한 최소 갯수

 

전이 방향은 자식에서 부모로 가야 하고 

-> dfs로 올라오기

-> u 서브트리는 u 자체도 포함하기 때문에 dp[u][1] = 1로 초기화하고 시작해야 함.

 

가능한 전이 조건은 2가지가 존재한다.

1)  현재 노드에 물건 없음 -> 자식이 반드시 물건을 골라야 하므로 자식이 물건을 고른 상태를 dp[ 현재 노드 ] 에게 더함

2) 현재 노드에 물건 있음

-> 자식에서 물건을 고를 수도 있고 안 고를 수도 있는데 최소가 되어야 하니까 

자식의 서브트리 상에서 두 상태 중 최솟값을 dp[ 현재 노드 ] 에 더함. 

---

문제 - 트리의 서브트리

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-subtree-of-tree/description

트리의 서브트리 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,R,Q;
    static boolean[] v;
    static ArrayList<Integer>[] g;
    static int[] dp;

    // dp 채우기
    // dp[ci] = ci를 루트로 갖는 하위의 정점의 수 + 1 (자기자신)
    static int dfs(int ci){
        int tot = 0;
        for(int n : g[ci]){
            if(v[n])
                continue;
            v[n] = true;
            tot += dfs(n);
        }
        dp[ci] = 1 + tot;
        return dp[ci];
    }

    public static void main(String[] args) throws IOException{
        N = read();
        //root
        R = read();
        // Q개의 쿼리 들어옴 
        Q = read();

        v = new boolean[N+1];
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        dp = new int[N+1];
        v[R] = true;
        int tot = dfs(R);

        StringBuilder sb = new StringBuilder();
        while(Q-->0){
            sb.append(dp[read()]).append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

트리에서의 서브트리 에 속한 정점 갯수를 세는 문제인데 쿼리 수가 많아서 dp로 한번 채우고 재사용하려 한다. 

-> dp [ i ] = i를 루트노드로 갖는 서브트리의 정점 갯수

 

dfs로 돌면서 채우는데 tot 은 하위 트리에서의 정점 갯수 총합이고 

트리는 원래 무방향 그래프라서 dfs 과정에서 부모 노드를 제외한 인접 노드들을 자식 노드라고 간주하고 탐색한다.

모든 자식을 돌며 tot을 채우면, i의 서브트리 = 노드 i  + 노드 i의 자식 노드들의 서브트리의 합 이므로

dp [ curIdx ] = 1 + tot 으로 갱신한다. 

---

문제 - 트리 전달

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-tree-forwarding/description

트리 전달 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[] parent;
    static ArrayList<Integer>[] g;
    static int[] toAdd;
    static int[] rst;

    // tot = 부모들로부터 누적되어 내려온 점수 증가량
    static void dfs(int ci, int tot){
        tot += toAdd[ci];
        rst[ci] = tot;

        for(int n : g[ci]){
            if(n == parent[ci])
                continue;
            dfs(n, tot);
        }
    }

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

        parent = new int[N+1];
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();
        
        for(int i = 1; i<=N; i++){
            parent[i] = read();
            if(parent[i] != -1){
                g[parent[i]].add(i);
                g[i].add(parent[i]);
            }
        }
        
        //1이 루트라고함
        toAdd = new int[N+1];
        rst = new int[N+1];
        while(M-->0){
            int i = read();
            int w = read();
            // i번 노드에 더해야할 점수 갱신
            toAdd[i] += w;
        }

        dfs(1,0);
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i<=N; i++){
            sb.append(rst[i]).append(" ");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

부모가 명확하게 주어지므로 parent를 통해서 부모로 못가게 막고 그래프를 양방향으로 생성함. 

문제는 연산 i, w가 주어지면 i를 루트로 하는 서브트리에 재귀적으로 next, w 연산이 됨

toAdd[i] = 노드 i에서 수행된 연산들의 합

쿼리마다 그 값을 합산해서 toAdd 에 노드마다 더함

 

DFS로 현재 노드 번호, 부모로부터 내려온 더해야할 값 합 을 파라미터로 받아서 

rst를 결과값 배열이라 하면 한번의 dfs로 toAdd 배열을 참고해서 갱신한다.

-> rst [ i ] = 노드번호 i에서 갖는 값의 합, 풀어 쓰면 다음과 같다. 

 rst [i] = 현재 노드 번호에서 더해야할 값 + 부모로부터 내려온 더해야할 값의 합

---

문제 - 중앙 노드 (구현이슈)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-median-node/description

중앙 노드 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N, R;
    static ArrayList<Integer>[] g;
    static int[] dp;

    static int findMid(int ci, int p){
        // 인접노드니까 자식수는 부모빼고 (-1)
        int size = g[ci].size()-1;
        if(p == -1)
            size += 1;

        if(size >= 2 || size == 0)
            return ci;
        
        for(int n : g[ci]){
            if(n == p)
                continue;
            return findMid(n, ci);
        }

        return 0;
    }

    static int dfs(int ci, int prev){
        int tot = 0;
        for(int n : g[ci]){
            if(n == prev)
                continue;
            tot += dfs(n, ci);
        }
        dp[ci] = 1 + tot;
        return dp[ci];
    }

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

        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();
        
        for(int i = 0; i<N-1; i++){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        // 중앙 노드를 구하고
        int mid = findMid(R, -1);
        dp = new int[N+1];

        ArrayList<Integer> li = new ArrayList<>();
        // mid의 자식노드를 각자 루트로 갖는 서브트리 크기를 dfs로 계산하고
        // list에 저장하고 정렬해서 [size-1]-[0]
        for(int n : g[mid]){
            li.add(dfs(n,mid));
        }
        Collections.sort(li);
        System.out.print(li.get(li.size()-1) - li.get(0));
    }
}

사고의 흐름

문제에서 최초 루트에서 시작해서 처음으로 자식의 갯수가 2개 이상이거나 없으면 쭉 타고 내려가서 자식이 0개인 리프노드를 중앙노드라고 정의함. 이 중앙 노드의 자식 노드를 루트 노드로 하는 서브트리의 크기를 전부 구해서 그중 max - min 을 구하기.

1) findMid 함수 구현해야함

2) 서브트리 dp로 값 재사용해서 정점수 세는 거 구현해야함

 

풀이

findMid 함수는 양방향 그래프로 입력받은 트리를 따라가면서 

현재 노드가 최초 노드가 아닌 경우에만 부모가 존재하므로 g[curIdx] 의 크기에서 -1 을 해줘야 한다. 

그리고 이게 2 이상이거나 0이면 바로 현재 ci를 리턴한다.

아니라면 자식 노드들을 타고 내려가서 그런 조건을 만족할 때까지 재귀적으로 계속 탐색한다.

-> return 0은 int 형으로 함수 선언하느라 아무 값이나 넣었다.

-> 문제 조건상 반드시 리프 또는 분기점에 도달하므로 해당 return문은 실행되지 않는다.

 

dfs 함수는 서브트리 정점수를 세기 위해 존재하는 함수인데 

mid가 새로운 루트노드이기 때문에 이걸 부모로 간주하고 모든 자식에 대해 서브트리 크기를 list로 저장하고

정렬해서 맨 끝값 - 맨 처음값을 하면 정답이 된다.

---

문제 - 정점 순회 (다시 풀기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-node-traversal/description

정점 순회 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,S,D;
    static ArrayList<Integer>[] g;
    // static int[] dist;
    static int ans = 0;

    // 현재 노드에서 서브트리 내 가장 깊은 리프까지 거리 반환하기
    static int dfs(int ci, int parent){
        int maxD = 0;
        boolean leaf = true;

        for(int n : g[ci]){
            if(n == parent)
                continue;

            leaf = false;

            int childD = dfs(n, ci) + 1;
            // 자식 거리가 D 넘어가면 그 자식까지는 가야함
            if(childD > D){
                // ci->n + n->ci
                ans += 2;
            }
            maxD = Math.max(maxD, childD);
        }

        // 리프노드면 갈 곳 없음. 거리 0
        if(leaf)
            return 0;

        return maxD; 
    }

    public static void main(String[] args) throws IOException{
        N = read();
        S = read();
        D = read();
        g = new ArrayList[N+1];
        //dist = new int[N+1];

        for(int i=1; i<=N; i++)
            g[i] = new ArrayList<>();

        for(int i = 0; i<N-1; i++){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }
        
        dfs(S, -1);
        System.out.print(ans);
    }
}

사고의 흐름

처음에는 색칠되지 않은 정점까지 직접 이동해야 한다고 생각했다.

그래서 S로부터 각 정점까지의 거리 dist를 구한뒤 dist > D인 리프까지 실제로 이동해야한다고 가정하고 풀었는데 

좀 안맞고 이상했다.

-> 여기서 좀 헤맸다 대체 뭘로 dp를 저장하던가 아니면 서브트리를 나타내야 하는가를 고민했는데

-> dfs의 그 반환값 자체가 해당 서브트리의 정보 로 사용할 수 있다는 점을 활용한다. (dp 역할)

 

풀이

현재 노드를 기준으로

1) 어떤 자식 방향의 가장 깊은 리프까지 거리가 D 이하라면

-> cur에서 색칠하면 해당 서브트리 전체가 커버되어서 해당 간선을 사용할 필요가 없음.

2) 가장 깊은 리프까지 거리가 D 초과라면

-> cur에서 색칠해도 닿지 않아서 해당 간선 이동이 필요함.

 

그리고 dp의 정의 부분처럼 dfs 자체가 서브트리의 정보를 나타낸다고 했으니

dfs 함수의 정의를 제대로 짚고 넘어가야 한다.

dfs(cur, parent) = 현재 노드 cur에서 서브트리의 가장 깊은 리프까지의 거리

위와 같이 정의하면 리프 노드는 0을 반환하고

자식 방향의 깊이 = dfs(next, cur) + 1로 나타낼 수 있다. 

그리고 모든 자식의 깊이를 비교해서 최댓값으로 갱신하고 반환하면 된다.

 

자식 방향의 깊이를 기준으로 해서 어떤 간선(자식-현재)을 실제로 지나가야 하는가를 알아야 하고, (cur->next)

다시 시작점으로 돌아와야한다고 했으므로 (next->cur) 인데 간선의 길이는 모두 1이라 했으니 

-> ans (총 거리) += 2

 

시간 복잡도는 모든 정점을 한번씩 방문하므로 O(N)

---

문제 - 노드의 값(트리 내에서 flow)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-value-of-node/description

노드의 값 설명 | 코드트리

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

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static int[] A;
    static ArrayList<Integer>[] g;
    static long ans = 0;

    /*
    필요한 연산량을 방향성으로 구별함
    현재 전이 방향은 dfs 구현상 자식 - 부모니까 
    */
    static long dfs(int ci, int parent){
        int cur = A[ci]-1;
        for(int n : g[ci]){
            if(n == parent)
                continue;
            cur += dfs(n,ci);
        }
        ans += Math.abs(cur);
        return cur;
    }


    public static void main(String[] args) throws IOException{
        N = read();
        A = new int[N+1];
        for(int i=1; i<=N; i++){
            A[i] = read();
        }

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

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        dfs(1,-1);
        System.out.print(ans);
    }
}

사고의 흐름

주어진 예제중에 하나의 노드에 초기값이 N이고 나머지가 0인 예제를 통해 관찰을 일단 해 봤다. 

문제는 N개의 노드가 있는 트리 모양의 연결 그래프의 모든 노드를 1로 만들고 싶어 하고 초기 노드 값이 주어진다.

따라서 1로 만들기 위한 변화량은 다음과 같다.

-> diff[ u ] = A[ u ] - 1

 

관찰

예제를 보면 4번 노드에 자식 노드가 7,8,9번이 달려있고 부모 노드가 2이다. 

4번 노드의 초깃값은 9이고 나머지는 0이다. 

자식 노드가 필요로 하는 변화량은 -1이고 모든 자식을 처리하고 나면 -3 6이 된다.

이제 부모인 2번이 4번(현재 6)을 1로 만들어 주려면

4번 서브트리의 잉여량 5가 부모와 연결된 간선을 통해 이동한다. (변화량)

-> 부모 노드 처리량 += 자식노드 처리량 (초기값 A[u] - 1)

-> 전이 방향은 자식에서 부모라는 것을 알 수 있고 이는 post order dfs와 같다. 

 

풀이

관찰한대로 옮겨보면 자식-> 부모 방향의 flow를 계산하는 느낌으로 접근할 수 있다. 

트리 위에서 surplus(여유) / deficit(부족) 를 계산하는 문제라고 볼 수 있다.

 

diff의 정의를 다시 보면 A[ u ] - 1인데

양수이면, 현재 노드에서 처리할 것이 남았으니 부모로 올려보내고

음수이면, 현재 노드에서 처리할 것이 부족하니 부모에서 데려와야해서 누적량에서 빠지게 된다. 

-> cur = 현재 노드를 루트로 갖는 서브트리에서의 필요한 잉여/부족량

 

1) 현재 노드에서 일단 초기 필요 변화량을 계산한다. (cur = A[u] - 1)

2) 모든 자식 노드에서 재귀적으로 필요 변화량을 계산해서 cur 에 합산한다.

-> 변화량에는 부호가 있어서 음수도 그냥 더해줌으로써 필요 변화량에서 빠지는 것을 표현할 수 있다.

3) 변화량의 크기 자체는 어차피 해야하는 연산량이라서 자식까지 다 보고 난 cur의 절댓값을 취해 총 연산 횟수에 합산.

4) 부호가 달린 변화량을 리턴한다. 

-> 현재 노드를 서브트리의 루트로 갖는 서브트리에서의 필요 처리량

---

문제 - 인접한 정점 (독립 지배 집합, 다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-adjacent-node/description

인접한 정점 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static int[] A;
    static ArrayList<Integer>[] g;
    static int[][] dp;
    // 그냥 Integer.MIN_VALUE 쓰면 오버플로 발생함..
    static final int INF = 10_000 * 10_000 + 1;

    static void dfs(int ci, int parent){
        dp[ci][0] = A[ci];
        
        int sum1 = 0;
        int sum2 = 0;
        boolean picked = false;
        int best = -INF;
        boolean hasChild = false;

        for(int n : g[ci]){
            if(n == parent)
                continue;
            hasChild = true;
            dfs(n, ci);

            // state 0
            dp[ci][0] += dp[n][1];

            // state 1
            sum1 += Math.max(dp[n][0], dp[n][2]);
            
            // state 2
            if(dp[n][0] >= dp[n][2]){
                picked = true;
                sum2 += dp[n][0];
            }
            else
                sum2 += dp[n][2];

            best = Math.max(best, dp[n][0] - dp[n][2]);
        }

        dp[ci][1] = sum1;

        // 리프노드면 자식중에 아무도 선택할수가 없음
        // 따라서 [2]의 경우에는 최솟값이 됨
        if(!hasChild){
            dp[ci][2] = -INF;
            return;
        }

        if(picked)
            dp[ci][2] = sum2;
        /* 
        적어도 하나는 자식에서 선택해야하는데 max로 고르면 [2]만 선택될 수 있어서
        그나마 손실이 가장 적은 선택된 자식의 값으로 교체하기 
        (dp[n][0] - dp[n][2] 니까 그 당시의 [2] 빠지고 [0] 추가되니 그냥 더하면됨)
        */
        else
            dp[ci][2] = sum2 + best;

    }

    public static void main(String[] args) throws IOException{
        N = read();
        A = new int[N+1];
        for(int i= 1; i<=N; i++)
            A[i] = read();

        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();
        dp = new int[N+1][3];

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        dfs(1,-1);
        // state 1은 부모를 선택함인데 루트는 부모가 없음
        System.out.print(Math.max(dp[1][0], dp[1][2]));
    }
}

사고의 흐름

1) 선택한 정점끼리 인접해있으면 안됨

2) 선택하지 않은 정점은 최소 하나의 선택한 정점과 인접해야 함

문제의 조건을 그대로 생각하고 풀어나가면 부모 , 현재, 자식 3개의 노드를 두고 생각해야 한다.

선택한 정점에 적힌 수의 합을 최대화하고자 할 때 그 최댓값을 구하는 문제이다.

 

풀이

먼저 가능한 상태를 생각해 보면 부모 p, 현재 u, 자식 v라고 하자.

dp의 정의는 다음과 같다.

dp[N][3] = 3가지의 state에 따른 u를 루트노드로 갖는 서브트리의 노드 값의 최대 합

 

0) u 선택 함, p 선택 안함

u를 선택했으니 초기값은 A[u] 이고,

문제 조건 1번과 dp 상태에 따라 자식이 가능한 상태는 dp[v][1] 뿐이다.

-> dp[u][0] += dp[v][1]

 

1) u 선택 안함, p 선택 함

u를 선택하지 않았으니 초기값은 0이고,

문제 조건 2번과 dp 상태에 따라 u는 부모에 의해 이미 커버되었으므로 자식은 선택이 되든 안되든 상관없다.

하지만 최댓값을 찾는 문제이므로 자식이 가능한 상태는 dp[v][0], dp[v][2] 이다.

-> dp[u][1] += max(dp[v][0], dp[v][2])

 

2) u 선택 안함, p 선택 안함

u를 선택하지 않았으니 초기값은 0이고,

문제 조건 2번에 따라 부모가 커버해주지 않았으므로 최소한 자식 1명이 커버해주어야 한다.

자식이 가능한 상태는 dp[v][0], dp[v][2] 이다.

-> 최댓값을 구해야 하니 기본적으로는 dp[u][2] += max(dp[v][0], dp[v][2]) 이다.

 

허나, dp[v][0]이 자식이 선택되는 상태인데 dp[v][2]만 골라지면 문제 조건을 충족시킬수가 없다. 

따라서, 임시 변수 sum2를 두고, loss = dp[v][0] - dp[v][2] 를 매번 최소화해서 갱신시켜서 저장해둔다. 

-> loss는 dp[v][2]가 dp[v][0] 보다 크지만 dp[v][0]을 최소 한 개는 골라야 한다면 loss가 가장 적을때의 dp[v][2]를 sum2에서 제거하고 dp[v][0]을 더하는게 문제 정답 조건을 만족하기 때문이다.

 

매번 둘 중 큰 값을 더할때마다 만약 dp[v][0]이 골라진 적이 있다면 dp[u][2] = sum2이고

dp[v][0]이 한번도 dp[v][2] 보다 큰 적이 없다면 dp[u][2] = sum2 + best이다.

 

구현 주의점

자식이 먼저 계산되어 있어야 하므로 visited 체킹을 하고 나서 바로 재귀적으로 dfs call을 넣어야 한다. 

-> 그렇지 않으면 dp 계산은 자식 서브트리 값에 의존하기 때문에 진행할 수 없다.

 

공식 해설과 비교

공식 해설은 현재 노드가 정확히 선택이 됬는지 / 안 됬는지를 나눠 2 state로 풀이한다.

dp[i][j] = i번을 루트 노드로 갖는 서브트리에서 
[i][0]은 i번 노드를 선택하지 않은 상황, [i][1]은 i번 노드를 선택한 상황일 때, 
조건을 만족하며 얻을 수 있는 최대 점수

 

문제 조건 2번은 최댓값을 구하면 절대 일어날 수 없는 상황이라고 설명한다. 

2) 선택하지 않은 정점은 최소 하나의 선택한 정점과 인접해야 함

 

귀류법을 활용한 설명

만약 문제 전체의 최적해인 최댓값이 존재하는데, 2번 조건을 만족하지 않는다고 가정한다.

-> 어떤 선택되지 않은 한 정점 v가 자신과 인접한 모든 정점이 선택되지 않았다는 상황이다.

 

이 상황에서 v를 선택하게 되면 

조건 1을 만족한다. -> 어떤 선택된 정점끼리도 인접하지 않는다.

모든 가중치는 양수이므로 현재 최적해 + A[v], 즉 증가하고 새로운 최적해가 등장한다.

-> 최적해가 이미 존재한다고 가정했는데 더 큰 최적해가 등장하므로 모순이 발생한다. 

 

따라서 선택되지 않았고 선택 정점과도 인접하지 않은 정점이 존재할 수 없다.

그러므로 항상 v 정점을 고르는게 최적해를 찾는 방법이 되고 

그러한 방법이 자동으로 조건 2를 만족시킨다.

---

문제 - 이진 트리 최대 경로 합(다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-binary-tree-maximum-path-sum/description

이진 트리 최대 경로 합 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static ArrayList<Integer>[] g;
    static int[] A;
    // 가중치 음수라서 가능한 최소값 계산해서 잡기
    static int ans = -1000 * 30_000 - 1;

    static int dfs(int ci, int parent){
        int best1 = 0;
        int best2 = 0;

        for(int n : g[ci]){
            if(n == parent)
                continue;
            
            int child = dfs(n, ci);
            if(child > best1){
                best2 = best1;
                best1 = child;
            }
            else if(child > best2){
                best2 = child;
            }
        }
        // 자식 다 돌고 밖에서 해야함
        // 가중치가 음수일때 처리해야함 !!
        ans = Math.max(ans, A[ci] + Math.max(0, best1) + Math.max(0, best2));
        return A[ci] + Math.max(0, best1);
    }

    public static void main(String[] args) throws IOException{
        N = read();
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();
        
        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        A = new int[N+1];
        for(int i =1; i<=N; i++){
            A[i] = read();
        }

        // dp = new int[N+1];
        dfs(1,-1);
        System.out.print(ans);
    }
}

사고의 흐름

특정 노드와 특정 노드 사이 경로상에 존재하는 모든 노드의 합을 최대로 할때 그 값을 구하기.

가능한 최대 경로 후보의 모양은 현재 노드를 중점으로 꺾이는 경로로 가는 것이다. 

 

그러나 자식이 부모에게 값을 전파할 때는 문제의 경로가 단순 경로이기 때문에 

자식 노드 + 자식 노드의 자식노드중 최댓값 을 부모에게 전파해야 한다.

-> dfs(u, parent) = u 에서 시작해서 아래 방향으로만 이동하는 경로들 중 최대 경로 합

 

풀이

입력에서 가중치가 [-1000, 1000] 이므로 최소 INF값은 30,000 * -1000 -1이 되고 이를 최대 경로합의 초기값으로 한다.

트리이므로 ArrayList 배열을 사용해 무방향 그래프의 형식으로 입력을 받고 

visited 처리는 이전 노드를 사용해서 처리한다. 

 

top 2는 최대로 갱신하는 거라 0을 초기값으로 두고 best1, best2라고 둔다.

이진 트리에서 현재 노드를 통해 만들 수 있는 최대 경로는 자식 방향 최대 경로 중 가장 큰 두개를 사용하는 경우이므로 

left right 구분 없이 top 2 두개를 더해주면 된다.

 

자식 방향으로 뻗는 가지의 노드의 최대합중 가장 큰걸 best1, 두번째를 best2라 하자. 

여기서 최대로 갱신하고 싶다 했으니 만약 자식쪽으로 방향을 택했는데 가중치의 합이 음수라면 

그냥 선택하지 않으면 될 것이다.

최대 경로 합 = max(기존 최적해, A[curIdx] + max(0, best1) + max(0, best2))

-> 이건 자식 순회 다 끝나고 for 밖에서 해줘야 한다.

 

그리고 리턴해주는건 부모에게 가는 값이니까 A[ curIdx ] + max(0, best1) 을 해주면 된다.

---

문제 - 인접한 노드 2(백준 2213 트리의 독립집합)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-adjacent-node-2/description

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static int[] A;
    static ArrayList<Integer>[] g;
    static int[][] dp;
    static int max;

    static void dfs(int ci, int parent){
        for(int n : g[ci]){
            if(n == parent)
                continue;
            dfs(n, ci);
            dp[ci][0] += Math.max(dp[n][0], dp[n][1]);
            dp[ci][1] += dp[n][0]; 
        }
    }

    
    // 부모가 선택 안된 경우만 지금 선택 가능
    static ArrayList<Integer> path = new ArrayList<>();
    static void find(int ci, int parent, boolean parentSelected){
        boolean selected = false;
        // [1]이 더 크면 현재를 선택해야함
        if(!parentSelected && dp[ci][1] > dp[ci][0]){
            selected = true;
            path.add(ci);
        }

        for(int n : g[ci]){
            if(n == parent)
                continue;
            find(n, ci, selected);
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        A = new int[N+1];
        for(int i = 1; i<=N; i++){
            A[i] = read();
        }        
        g = new ArrayList[N+1];
        for(int i=1 ;i<=N; i++)
            g[i] = new ArrayList<>();

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        dp = new int[N+1][2];
        for(int i =1 ; i<=N; i++){
            dp[i][1] = A[i];
        }

        dfs(1, -1);
        max = Math.max(dp[1][0], dp[1][1]);

        find(1,-1,false);
        //정렬조건빼먹지말기
        Collections.sort(path);

        StringBuilder sb = new StringBuilder();
        sb.append(max).append("\n");
        for(int n : path){
            sb.append(n).append(" ");
        }
        System.out.print(sb);
    }
}

사고의 흐름

백준 2213 트리의 독립집합 문제이다. 난이도는 골드 1인가 2로 기억하고 있다.

조건 1 ) 선택된 정점끼리 인접하면 안된다. 

위 조건을 만족하면서 트리에서의 정점을 적절히 선택하여 정점 값의 최대 합을 구하는 문제이다.

그리고 그 최대합을 갖는 정점 집합이 유일할 때, 해당 집합에 소속된 정점을 오름차순 정렬하여 출력해야 한다.

 

조건 1에 의해서 점화식을 생각해보면

1) 현재 노드를 선택하면 자식노드에서는 무조건 선택을 할 수 없다. 

2) 현재 노드를 선택하지 않으면 자식노드에서 선택을 해도 되고 안해도 된다.

다만 최댓값으로 갱신해야 하므로 둘 중 각자의 서브트리에서의 조건에 맞게 선택하는 정점 값의 총 합 중 큰걸 선택하면 된다.

 

경로 복원의 경우엔 처음에는 최단경로에서의 복원처럼 하려고 했다. 

그니까 현재 dp 값과 자식 dp값을 비교해서 조건에 맞게 선택하는 방식으로 하려고 했는데 

트리 dp는 최적해의 조합을 이은 경로가 여러 갈래로 찢어질 수 있어서 불가능하다. 

-> 트리 DP는 여러 서브트리의 최적해의 조합으로 이루어진다.

 

풀이

dp[parent][0] += max(dp[child][0], dp[child][1]);
dp[parent][1] += dp[child][0];

위와 같이 점화식을 나타낼 수 있고 

for문에서 visited 체킹하고 바로 dfs 들어가고 나와서 dp값을 갱신하는 방식으로 최대합을 구하면 된다.

 

복원의 경우엔 dfs로 하는데 

현재 노드, 부모 노드, 부모 노드 선택여부 3가지 상태를 들고 판단한다.

방향은 현재 -> 자식 방향이기 때문에 

dfs 들어오자마자 현재에 대해서 처리해줘야 한다.

 

부모 상태가 선택 안 된 상태일때만 현재를 고를 수 있고,

부모가 선택되지 않았으면 자식 상태 (여기서는 현재를 의미)를 고르는 것이 자유롭다.

따라서, 현재를 고른 상태가 현재를 안 고른 상태보다 클 때만 골라서 path에 저장한다.

if(!parentSelected && dp[ci][1] > dp[ci][0]){
    selected = true;
    path.add(ci);
}

 

selected라는 현재 고른 상태를 저장하는 변수를 만들어서 

자식에 대해 순회할 때 

dfs ( nextIdx, curIdx, selected ) 로 재귀적으로 처리하면 된다.

---

문제 - 인접하지 않게 색칠하기 (트리에서의 배낭 DP) (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-coloring-not-adjacently/description

인접하지 않게 색칠하기 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,K;
    static long[] A;
    static ArrayList<Integer>[] g;
    static long[][][] dp;
    static final long INF = -(1<<60);

    static int[] sz;

    static void dfs(int u, int parent){
        sz[u] = 1;

        for(int i = 0; i<2; i++){
            Arrays.fill(dp[u][i], INF);
        }
        dp[u][0][0] = 0;
        dp[u][1][1] = A[u];

        // 현재까지 merge 완료된 u쪽 노드 갯수
        int curSize = 1;

        // 배낭 부분해 merge
        for(int v : g[u]){
            if(v == parent)
                continue;
            dfs(v, u);
            
            long[][] next = new long[2][K+1];
            // 반드시 초기화해줘야 함
            for(int i = 0; i<2; i++){
                Arrays.fill(next[i], INF);
            }

            // 서브트리 내 노드수로 순회 최적화
            for(int i = 0; i<=Math.min(curSize, K); i++){
                for(int j = 0; j<=Math.min(sz[v], K-i); j++){
                    // 현재가 선택 안됬으면 자식은 선택해도 되고 안해도 되는데 그중 큰거 
                    if(dp[u][0][i] != INF){
                        long bestChild = Math.max(dp[v][0][j], dp[v][1][j]);
                        if(bestChild != INF)
                            next[0][i+j] = Math.max(next[0][i+j], dp[u][0][i] + bestChild);
                    }
                    
                    // 현재가 선택됬으면 자식은 선택하면 안됨.
                    if(dp[u][1][i] != INF && dp[v][0][j] != INF)
                        next[1][i+j] = Math.max(next[1][i+j], dp[u][1][i] + dp[v][0][j]);
                }
            }

            dp[u] = next; 
            curSize += sz[v];
        }
        sz[u] = curSize;
    }

    public static void main(String[] args) throws IOException{
        N = read();
        sz = new int[N+1];
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        A = new long[N+1];
        for(int i = 1; i<=N; i++){
            A[i] = read();
        }
        K = read();

        dp = new long[N+1][2][K+1];
        dfs(1, -1);
        long ans = INF;
        for(int i =0; i<2; i++){
            for(long sum : dp[1][i])
                ans = Math.max(ans, sum);
        }
        System.out.print(ans);
    }
}

사고의 흐름 

색칠한 노드가 서로 인접하지 않아야 하고 색칠한 노드의 갯수가 K개를 넘어서는 안 될 때, 

색칠된 노드의 합이 최대로 되는 값을 구하기 

인접한 정점끼리는 동시에 선택될 수 없으므로, 부모 노드의 선택 여부가 자식 노드의 가능한 상태를 결정한다.

그리고 색칠된 노드 갯수 제한이 있으므로 부모 색칠 갯수 + 자식 색칠 갯수 <= K에서 전부 해봐야 한다.

 

풀이 : 트리 위의 배낭 DP

일단 상태를 정의하고 점화식을 세워보면 다음과 같다.

dp[u][c][k] 
= 노드 u를 루트로 가지는 서브트리 내에서 
현재 노드의 색칠된 상태가 c이고, 
색칠한 노드 수의 정확한 갯수가 k일때,
색칠된 노드의 값의 총 합이 최대로 될 때의 값

-> c = 0 (현재 노드 선택 X), c = 1 (현재 노드 선택 O)

 

트리 DP는 현재까지의 부분해와 자식의 부분해를 merge하면서 최적해를 구한다.

현재까지 merge된 부모 쪽 서브트리에서 선택한 노드 수를 i라 하고,

자식 서브트리에서 선택한 노드의 갯수를 j라고 하면 i+j 는 K 이하가 되어야 한다. 

for(i)
    for(j)
        next[i+j] = old[i] + child[j]

 

초깃값은 불가능한 상태들이 있기 때문에 INF = -(1L<<60) 로 invalid 한 값으로 설정해두고 

next와 dp를 초기화할 때 반드시 써 줘야 한다. 

-> dp[u][1][1] = A[u] ( 1개 선택 ), dp[u][0][0] = 0 (아무것도 선택하지 않음)

 

현재 자식을 merge하면서 갱신된 값(상태)이 같은 자식 merge 중 다시 사용되는 것을 막아야 한다.

그걸 방지하기 위해서 현재 자식 v까지 merge 한 결과를 임시 저장하는 배열 next를 써야 한다.

dp[u] 에는 이전까지 처리한 자식들의 상태가 저장되어 있으니 이걸 고려해서 가능한 상태를 써 보면

next[0][i+j] = max(next[0][i+j], dp[u][0][i] + max(dp[v][0][j] , dp[v][1][j]);
next[1][i+j] = max(next[1][i+j], dp[u][1][i] + dp[v][0][j]);

 

그렇게 자식 하나에 대한 병합과정이 끝났으면 

dp[u] = next

-> u의 자식 v까지 merge 해 준다.

 

순회 최적화

K 제한때문에 i <= K && i+j <=K 로 순회를 해주고 있는데 

사실 한 서브트리 내에서 선택할 수 있는 노드 갯수는 서브트리 자체의 크기를 넘을 수 없다. 

sz[u] = u 서브트리 크기로 정의하고,

따라서 자식을 하나 처리해줄 때 마다 curSize += sz[child]을 해주고,

자식 순회가 다 끝나면 sz[current] = curSize를 해준다.

for(int i = 0; i<=Math.min(curSize, K); i++){
    for(int j = 0; j<=Math.min(sz[v], K-i); j++){

-> 불가능한 상태를 순회하지 않도록 줄이는 상수 최적화

 

 

각 간선마다 배낭 merge -> O(K^2) 이므로

전체 시간 복잡도 = O(N * K^2)

---

문제 - 노드 최적의 갯수 (최소 지배 집합)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-node-best-count-3/description

노드 최적의 개수 3 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static ArrayList<Integer>[] g;
    static int[][] dp;
    static final int INF = 100_000 * 100_000 + 1;

    // leaf 명시적으로 처리 꼭 하기
    static void dfs(int u, int parent){
        dp[u][2] = 1;

        boolean found = false;
        boolean isLeaf = true;
        int minLoss = INF;

        for(int v : g[u]){
            if(v == parent)
                continue;

            isLeaf = false;
            dfs(v, u);

            dp[u][0] += Math.min(dp[v][1], dp[v][2]);
            dp[u][2] += Math.min(Math.min(dp[v][0], dp[v][1]), dp[v][2]);

            if(dp[v][2] <= dp[v][1]){
                found = true;
                dp[u][1] += dp[v][2];
            }
            else
                dp[u][1] += dp[v][1];
            
            // dp[u][1]에서 [1]만 선택되어서
            // [2]를 선택해야하지만 그 손해가 가장 작을때를 저장
            minLoss = Math.min(minLoss, dp[v][2] - dp[v][1]);
        }
        if(isLeaf){
            dp[u][1] = INF;
            return;
        }

        if(!found)
            dp[u][1] += minLoss;
    }


    public static void main(String[] args) throws IOException{
        N = read();
        int M = N-1;
        g = new ArrayList[N+1];
        for(int i=1; i<=N; i++){
            g[i] = new ArrayList<>();
        }    

        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        dp = new int[N+1][3];
        dfs(1,-1);
        System.out.print(Math.min(dp[1][1], dp[1][2]));
    }
}

사고의 흐름

물건을 놓는다.. 모든 노드에 대해 자기 자신 혹은 인접한 노드 위에 최소 하나의 물건이 올라가 있어야 한다.

-> 간선 양 끝점 중 최소 하나의 노드는 선택되어야 함

이때 필요한 최소 선택된 노드의 갯수 구하기

-> minimal dominating set on Tree

 

풀이

부모 - 현재 - 자식 3개를 보고 현재 노드 u의 상태를 주어로 놓고 상태를 생각해보자.

dp[u][x] = u가 현재 어떤 상태인지를 정의했을 때, u를 루트노드로 하는 서브트리의 최소 비용

 

0) dp[u][0] = 부모 선택 o, 현재 선택 x, 자식 선택 x

-> u는 부모에 의해 cover된 상태

 

1) dp[u][1] = 부모 선택 x, 현재 선택 x, 자식 선택 o

-> u는 자식에 의해 cover되어야 하는 상태

 

2) dp[u][2] = 부모 선택 x, 현재 선택 o, 자식 선택 x

-> u 자기 자신에 의해 cover된 상태

 

전이의 경우는 자식의 입장에서 생각해보면 된다. 

 

0) dp[u][0] = u가 부모에 의해 cover된 상태라서 0,1,2 다 가능은 하지만 0의 정의에 의해 1,2만 가능

-> dp[u][0] += min(dp[v][1], dp[v][2])

 

1) dp[u][1] = u가 부모에게 cover되지 않았고, 스스로 선택하지도 않아 최소한 하나의 자식은 선택된 상태여야 함.

-> 0번과 같이 1,2가 가능하지만 최소한 한번은 [2]를 뽑아야 한다. 

따라서, minloss = min(minloss, dp[v][2] - dp[v][1])를 매번 계산해서 

[2]가 한번도 안 뽑혔을 때, dp[u][1] += minloss로 최대한 손해를 보지 않는 dp[v][2]를 더해 준다.

 

2) dp[u][2] = u가 스스로를 커버해서 자식은 어떤 상태이든 상관없다.

-> dp[u][2] += min(dp[v][0], min(dp[v][1], dp[v][2]))

 

정답은 상태 정의에 의해 [0]의 경우는 부모가 커버해주는 경우인데 

루트노드는 부모 노드 자체가 없으므로 불가능한 상태이다. 

-> ans = min(dp[1][1], dp[1][2])

 

최대 독립 집합 문제와의 비교

MIS(maximum independent set), vertex cover 문제 계열은 제약이 간선 단위이다. (부모 - 자식)

-> 서로 충돌하면 안되는 대상들을 최대한 많이 선택

현재 문제와 같은 Dominating Set 문제 계열은 제약이 정점 단위이기 때문에 (부모 - 현재 - 자식) 3 state 이상 필요.

-> 최소 수의 거점으로 전체를 관리/감시/서비스 하는 활용

---

문제 - 트리 위에 색칠된 정점 수

https://www.codetree.ai/ko/trails/complete/curated-cards/test-count-colored-node/description

트리 위에 색칠된 정점 수 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N, Q;
    static int LOG = 0;
    static ArrayList<Integer>[] g;
    static Set<Integer> ss = new HashSet<>();
    static int[] dist;
    static int[] depth;
    static int[][] parent;
    static StringBuilder sb = new StringBuilder();

    static void dfs(int u, int p){
        if(ss.contains(u))
            dist[u] += 1;
        parent[0][u] = p;
        for(int v : g[u]){
            if(v == p)
                continue;
            depth[v] = depth[u] + 1;
            dist[v] = dist[u];
            
            dfs(v, u);
        }
    }

    static void build(){
        for(int i = 1; i<LOG; i++){
            for(int u = 1; u<=N; u++){
                parent[i][u] = parent[i-1][parent[i-1][u]];
            }
        }
    }

    static int getLCA(int a, int b){
        if(depth[b] > depth[a]){
            int t = a;
            a = b;
            b = t;
        }

        int diff = depth[a] - depth[b];
        for(int i = LOG-1; i>=0; i--){
            if((diff & (1<<i)) != 0)
                a = parent[i][a];
        }

        if(a==b)
            return a;
        
        for(int i= LOG-1; i>=0; i--){
            if(parent[i][a] != parent[i][b]){
                a = parent[i][a];
                b = parent[i][b];
            }
        }

        return parent[0][a];
    }

    static int getDist(int a, int b){
        int c = getLCA(a,b);
        int nd = 0;
        if(ss.contains(c))
            nd = 1;
        return dist[a] + dist[b] - 2*dist[c] + nd;
    }
    

    public static void main(String[] args) throws IOException{
        N = read();
        while(N >= (1<<LOG))
            LOG++;
        g = new ArrayList[N+1];
        for(int i =1 ; i<=N; i++){
            g[i] = new ArrayList<>();
        }
        dist = new int[N+1];
        depth = new int[N+1];
        parent = new int[LOG][N+1];

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

        int k= read();
        while(k-->0)
            ss.add(read());
        
        dfs(1,0);
        build();

        Q = read();
        while(Q-->0){
            int a= read();
            int b = read();
            sb.append(getDist(a,b)).append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

트리 위에서 K개의 미리 색칠된 노드가 존재할 때, 특정 노드와 특정 노드로 가는 경로 위의 색칠된 노드 갯수를 구하는 문제이다.

주어진 그래프는 루트가 1번인 트리니까 경로는 유일하다. 

따라서, 가장 가까운 공통 조상 노드에서 한번 꺾게 된다. 이를 이용해서 풀어보면

dist[u] = 루트노드에서 노드 u까지 봤을때 색칠된 노드 갯수 합
depth[u] = 루트노드에서 노드 u까지의 깊이
parent[i][u] = 노드 u에서 2^i 만큼 위로 이동했을 때 도착하게 되는 노드 번호

라고 하자. 입력을 맨 왼쪽을 루트노드로 놓고 그림으로 그려보면 다음과 같다.

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

colored = 2 4 6 7 11

처음에는 dist[ a ] + dist [ b ] 면 공통 조상을 포함해서 색칠된 노드 총합이니까 

거기서 dist [ lca(a,b) ] * 2를 빼면 되겠다고 생각했다. 

그러나 그냥 빼기만 하면 만약에 LCA가 colored node라면 하나는 있어야 한다. 

최종 계산식은 다음과 같다. (ss는 colored node가 저장된 HashSet)

dist[a]+dist[b]-2*dist[lca(a,b)] + if(lcd(a,b) in ss)

---

Tree 챕터 완료 후기

DP하고 그래프를 많이 풀긴 했었는데 트리랑 이진트리는 많이 다루지 않았고 네트워크 위에서의 최적화나 최소, 최대 합, 갯수구하기 문제가 많이 약했었는데 이번 챕터를 공부하며 트리에 대한 이해가 깊어진 거 같다. 뭔가 더 깊게 파 보고 싶은데 BFS, DFS 탐색 최적화와 DP II를 다루고 나서 union-find, 크루스칼, prim 복습 빠르게 하고 위상정렬을 이용한 DAG DP로 넘어가면 될 것 같다.

 

일단 다음 주차에는 구현 관련해서 해결전략 쪽 문제 쭉 풀고 

그다음 주차에 MST, 위상정렬 둘 다 하고  롤링해시 한번 보고 Bitonic Cycle이랑 BitMask DP

요즘 또 그리디가 나오는데 DP 공부하면서 교환 논법, 최적해를 하나 선택했을 때 왜 안전한지에 대한 증명으로 공부를 하면

사실상 DP에서 최적화를 하면 그리디가 되니까 그것도 어느 정도는 될 것 같다. 

 

앞으로 이렇게 하면 될 듯

-> Trail 2-9 (해결전략) -> Trail 4-1 (구현) -> T 5-2 (Shorten Time Technique) -> T 5-4 (Greedy)

---

2차 갭체크 후기

1차 갭체크 결과

2차 갭체크 오전 결과 (1)

2차 갭체크 오후 결과 (2)

 

한 달 정도 코드트리로 공부하고 나서 얼마나 향상되었는지 갭체크를 통해 알아보기로 했다. 확실히 Trail 5까지의 기본 개념은 잘 다져졌는데 오늘 오전에 갭체크할때 마지막 문제에서 union-find 기반 크루스칼 2번 돌려가지고 cost의 타입이 0과 1이 있는데 0을 우선시해서 스패닝트리 하나 만들고 1을 우선시해서 스패닝트리 만들어서 조건상 cost의 max - min을 구하는 문제가 나왔었다. 아니 분명 채점 돌아가고 있는데 20분 딱 끝나서 틀렸다. 그래프랑 최단경로는 자신있는 알고리즘인데도 지식이 부족하다 어쩌고 해서 도저히 납득할 수 없어서 갭체크를 한번 더 봤다.

 

두 번째 갭체크에서 틀린 2번 문제는 LCA 문제인데 트리에서 세 정점을 서로 다른 컴포넌트로 만드는 정점을 찾는 문제였다. 다시 말하면 세 정점의 median(분기점)을 찾아서 그 정점을 제거했을 때 세 방향으로 실제로 갈라지는지 검증을 통해서 푸는 문제이다. 이것도 binary lifting + LCA 구현하고 세 점의 가장 깊은 LCA를 X라 할때 X가 a,b,c와 모두 다른지, a,b,c가 서로 진짜 다른 방향의 컴포넌트인지를 구분하는 함수까지 추가로 구현해야 한다.

 

 이걸 lca, 트리 지식 정도 있고 관찰로 해서 푼다면 20분은 이해가 안된다... 실제 코딩테스트에는 자동완성 IDE도 없을 뿐더러 템플릿용 개인 노트나 라이브러리도 제공되지 않는다. 타이머가 이게 맞나 싶지만 결국 본인 실력 문제라고 생각한다. 실제로도 7번의 레벨 21 문제보다 2번 문제가 17로 낮은걸 보면 그냥 lca 세개만 구하면 통과하는 그런 문제일거 같은데 외부에서 트리 응용 문제나 더 풀어야겠다.

 

첫번째 갭체크랑 비교했을 때 좀 어려운 DP같은게 나와주길 바랬는데 안나와서 좀 아쉽고 일단 트리랑 DP 감각같은건 좀 좋아진 것 같다. 그리고 문제 레벨도 약간 높아진 것 같다. 어쩌면 2번째 갭체크에서 2번문제 맞았으면 좀 더 어려운 문제가 갭체크에서 나왔을지도 모르겠다. 그리고 코드트리 문제 수가 은근 많아서 내가 부족한거만 본다고 해도 해야할 게 많은 것 같고 목표는 갭체크 열심히 봐서 지식이 부족하다는 결과가 안나오게 만들고 프로그래머스에 있는 카카오 기출  올솔할 수 있었으면 좋겠다.

 

 

#코드트리 #코딩테스트 #코테공부 #갭체크 #개발자취업 #코딩테스트준비