2533번 (Tree-dp)

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

2533번: 사회망 서비스(SNS)

이 문제는 상당히 생각하기 어렵다...

처음에는 어떻게 접근해야 하는지조차 몰랐었다.. 그래서 주변에 물어봐서 이해했다.

tree-dp를 처음 풀어본 문제는 아래의 문제였다.

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

15681번: 트리와 쿼리

아래 문제의 동작원리는 2533번보다는 간단한 tree-dp시작으로 좋은 문제로 추천을 받아서 배우면서 풀었다.

그래서 풀이 방법도 사람마다 다르다는걸 확실히 느꼈다.

 

그래서 15681번 부터 정리해보겠다.

이 문제는 요구하는 것은 간단하다. 주어지는 노드 갯수와, 트리수 그리고 쿼리(값을 얻고 싶은 노드),를 입력 받아서 자신을 포함한 자식노드 수를 출력하면 된다.

간선들 또한 주어진다.

그래서 먼저 초기의 준비는 dfs와 같다.

class Graph{
    int[] cache;
    LinkedList<Integer>[] adj;
    LinkedList<Integer>[] child;
    int n;
    boolean[] visit;

    public Graph(int n) {
        child = new LinkedList[n+1];
        for(int i=0; i<n+1; i++){
            child[i] = new LinkedList<>();
        }
        adj = new LinkedList[n+1];
        for(int i=0; i<n+1; i++){
            adj[i]=new LinkedList<>();
        }
        this.n = n;
        visit = new boolean[n+1];
        cache = new int[n+1];
    }

    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }
    ....
}

대신 인접노드를 저장한 리스트와 달리 자식노드를 저장할 리스트를 따로 만들었다.

그래서 자식 노드를 만들기 위해서 아래와 같이 dfs를 통해 자식 노드를 탐색하여 만들었다.

public void dfs(int R){
        visit[R]=true;
        for (int i : adj[R]) {
            if(visit[i])continue;
//            if(!visit[i]){
                child[R].add(i);
                visit[i]=true;
                dfs(i);
//            }
        }
    }

그 다음으로 자식 노드를 가지고 있는 리스트가 있으니 이를 이용해서 각 노드별로 자신을 포함한 자식노드의 수를 저장해둘 것이다.

public int dp(int R){
    if(cache[R]!=0)return cache[R];
    int sum = 0;
    for (int child : child[R]) {
        sum+=dp(child);
    }
    return cache[R] = sum + 1;
}

위의 코드는 이미 저장된 값이 있으면 값을 반환하고, 0이라면 노드의 자식노드 수를 세는 방식이다.

위 코드같은 경우는 leaf노드에 도달하면 값을 sum +1->1로 초기화한다.

 

또 다른 방법은 위의 자식노드 리스트를 만들지 않고, 방문처리와 자식노드 저장리스트를 하나로 묶은 방법이다.

public int dp2(int R){
    cache[R]=1;

    for(int i : adj[R]){
        if(cache[i]==0){
            cache[R]+=dp2(i);
        }
    }
    return cache[R];
}

동작 원리는 먼저 노드를 탐색하면서 1로 초기화시킨다. 그 다음 leaf노드에 도달하면, 1을 반환하고, 반환된 값은 부모노드에 더해진다.

예를 들어 노드 1의 자식 노드 2,3이 있다고 할때, 2와 3은 1로 초기화 되고, 그 값들은 1로 넘어와서 1은 3이된다.1+1+1(노드1에 있던)=3

 

 

위와같은 방식으로 노드에 저장될 값들을 저장할 리스트 cache를 만들어서 저장하는 방식으로 Tree-dp문제를 풀 수 있다.

 

그래서 이제 본론인 2533번의 설명을 해보겠다.

위의 문제가 간단한 계산 문제였다면, 이 문제는 응용문제이다.

원리는 같지만 계산이 다르다.

먼저 얼리아답터의 최소수를 구하기 위해서는 트리에서 현재노드가 얼리아답터인 경우와 아닌 경우로 나누어서 생각해야한다.

만약 현재 노드가 얼리아답터라면 자식 노드가 얼리아답터인지는 중요하지 않다.

만약 현재 노드가 얼리아답터라면 자식 노드가 얼리아답터이어야 한다.

위의 조건을 가지고 코드를 짜야한다.

 

이 문제도 마찬가지로 초기의 준비는 dfs와 비슷하다.

LinkedList<Integer>[] adj;

    int[][] dp;
    boolean[] visit;
    public Graph(int n) {
        adj = new LinkedList[n+1];
        for(int i=0; i<n+1; i++){
            adj[i] = new LinkedList<>();
        }
        dp = new int[n+1][2];
        visit = new boolean[n+1];
    }

    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }
    ...
}

여기서는 2차원 배열을 사용할 것이다.

왜냐하면 현재의 노드가 어리아답터인 경우와 얼리아답터가 아닌 경우를 나누어서 넣을 것이기 때문이다.

그래서 인접노드 리스트를 만들고, 이를 이용해서 방문처리 리스트와 노드값의 저장을 하는 리스트를 만들것이다.

그 다음은 아래의 코드처럼 DP와DFS를 합친 코드를 사용할 것이다.

public int[] dfs(int R){
    dp[R][0]=0;//자기자신이 얼리아답터가 아니다.
    dp[R][1]=1;//자기자신이 얼리아답터다.
    //leaf 노드 정의

    visit[R]=true;
    for (int i : adj[R]) {
        if(visit[i])continue;
        int[] tmp = dfs(i);
        dp[R][0]+=tmp[1];//자신이 얼리어 답터가 아니면 자식 노드는 모두 얼리아답터이다.
        dp[R][1]+=Math.min(tmp[0],tmp[1]);//자신이 얼리어 답터이면 아래에서 최소값을 가져온다.
    }
    return dp[R];
}

일단 노드를 탐색하러 내려가면서 모두 [0,1]로 초기화할 것이다. 그 다음 leaf노드에 도달하면 초기화한 값을 반환하여 다시 루트노드까지 돌아 올 것이다.

동작 방식은 아래 그림과 같다.(그림이 더럽지만...이해하길 바란다.)

위 그림에서 제일 처음 4번 leaf노드에 도달해서 2번 leaf노드로 돌아가는 과정을 보면, 먼저[0,1]로 초기화된 leaf노드에서 반환된 tmp int배열은 [0,1]을 저장하고 있다.

그래서 2번노드가 얼리아답터인 경우와 얼리아답터가 아닌경우를 조건에 맞게 처리하면,

2번 노드가 얼리아답터인 경우는 아래의 자식 노드가 얼리아답터이든 아니든 상관이 없다. 그러므로 자식노드가 얼리아답터인 경우와 얼리아답터가 아닌 경우 중에 작은 값을 가져온다. 즉, [0,1]중에 0을 가져오는 것이다. 그럼 2번 노드의 값은 [0,1]->[0,1]이된다. 즉, 그대로이다.

2번 노드가 얼리아답터가 아닌 경우는 아래의 자식 노드가 얼리아답터이어야 한다. 그래서 노드 4의 [0,1]중에 1을 가져온다. 그럼 2번 노드의 값은 [0,1]->[1,1]로 바뀐다. 이와 마찬가지로 5번 노드에 내려가서 같은 조건을 수행하면,

2번 노드는 [1,1]->[2,1]로 바뀐다. 그리고 6번까지 마저 수행하면 [2,1]->[3,1]이 된다. 즉 2번 노드가 얼리아답터이면 1개면 되고, 2번이 얼리아답터가 아니면 3개의 얼리아답터가 자식 노드에 있어야 하는 것이다.

이런 과정을 반복하여서 dp에 저장하고, 루트 노드에 값의 저장이 끝나면 루트노드가 얼리아답터인 경우와 아닌 경우중에 더 작은 값을 출력하면 결과값이 된다.

즉 루트 노드에는 자식 노드들 중에 얼리아답터인 경우의 갯수를 저장하는 것이다.

그래서 결과 코드는 아래와 같다.

package backjoon.b2533;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class b2533 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Graph g = new Graph(n);
        for(int i=0; i<n-1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g.addEdge(u,v);
        }
        int[] tmp = g.dfs(1);
        System.out.println(Math.min(tmp[0],tmp[1]));
    }
}
class Graph{
    LinkedList<Integer>[] adj;

    int[][] dp;
    boolean[] visit;
    public Graph(int n) {
        adj = new LinkedList[n+1];
        for(int i=0; i<n+1; i++){
            adj[i] = new LinkedList<>();
        }
        dp = new int[n+1][2];
        visit = new boolean[n+1];
    }

    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }

    public int[] dfs(int R){
        dp[R][0]=0;//자기자신이 얼리아답터가 아니다.
        dp[R][1]=1;//자기자신이 얼리아답터다.
        //leaf 노드 정의

        visit[R]=true;
        for (int i : adj[R]) {
            if(visit[i])continue;
            int[] tmp = dfs(i);
            dp[R][0]+=tmp[1];//자신이 얼리어 답터가 아니면 자식 노드는 모두 얼리아답터이다.
            dp[R][1]+=Math.min(tmp[0],tmp[1]);//자신이 얼리어 답터이면 아래에서 최소값을 가져온다.
        }
        return dp[R];
    }
}