[백준]22253: 👨‍🎨트리 디자이너 호석 - JAVA

[백준]22253: 트리 디자이너 호석

22253번: 트리 디자이너 호석

풀이

🪑 정말 어려웠다... 이 문제 때문에 오늘 하루를 다 날려버렸따 ㅎㅎ,, 하지만 새로운 유형인 트리DP에 대해서 깊게 이해할 수 있었던 시간이었다..!

 

📝 문제의 조건!

• 루트는 항상 1번 노드이다.
• 정점에는 0~9까지의 숫자가 쓰여있다.
• 임의의 부모 노드에서 자식 노드 까지 가는 경로에서 선택하는 숫자가 오름차순이 되는 경우의 수를 구한다.

숫자의 오름차순이 되는 경우...LIS가 떠올랐다. 이전에 비슷한 전구 문제 에서도 오름차순 순열을 구하는 문제가 있었는데 이건 그것과는 달리 트리 유형이라 매우 새로웠다. (사실 풀이 방법도 완전 다르다)

 

 

🙋‍♀️ 접근 방법을 시간순서대로 적어보겠다. 다양한 방법으로 생각해 보았다!

 

1. 첫번째로 생각해 보았던 방법은 BFS + DFS였다. 이때까지만 해도 DP라는걸 몰랐었다.

• 입력받은 간선의 정보로 루트 -> 리프로 향하는 트리를 만들어주었다. 
• BFS로 레벨 순회를 하며 깊이에 따라 이전 노드와 비교하며 현재 노드와 오름차순이 되는지, 된다면 누적해서 더해주도록 하였다.
• 문제점은 현재 노드와 오름차순이 되는지 확인할 때 루트부터 쭉 올라오며 모든 경우를 확인해 주어야 한다. 
• 이미 트리 생성할때 O(N)시간이 소요되었다. 노드를 탐색할 때와 합치면 O(N) + O(N^2) + a의 시간이 소요된다. 이 방법은 아니라고 생각했다.
• 코드를 작성하면서 이렇게 푸는게 아니라는 생각이 들 정도로 코드가 지저분하기도 했다 ㅎㅎ

 

2. 루트 -> 리프노드 방향으로 top-down 방식을 적용하였다.

• 방문 순서에 따라 결과값이 달라졌다. 
• bottom-up 시에 이미 계산한 결과는 저장이 되는데, 이게 문제를 발생시켰다.
• 예를들어 문제에 그려져있는 트리를 보면 1번(3) -> 6번(9)로 탐색 후 결과가 저장된 상태이다. 이때 1번 -> 3번 -> 7번 으로 탐색을 했다고 가정하면 7번노드는 6번과 관계가 없어야 하지만 계산 과정에서 6번의 결과값이 이미 저장되어 이후 연산에 영향을 미치게 된다.
• 그래서 노드 마다 결과값을 저장하는 배열을 따로 만들어 다른 경로에 영향을 미치지 않도록 하여야 겠다고 생각했다.

 

3. 그래서 이번엔 노드마다 결과값을 저장하는 배열을 따로 만들어 다른 경로에 영향을 미치지 않도록 하였다.

• 또 다른 문제점이 나타났다.
• 결과값이 리프노드에 분산되어 저장이 되기 때문에 같은 경로가 있다면 그 경우의 수의 값이 중복되어 계산된다.
• 예를들어 루트는 항상 모든 리프에 포함이 되었다.
• 따라서 결과는 한 곳에 몰아줘야 겠다고 생각했다. bottom-up 방식을 시도하였다.

 

 

🔧 DP로 문제를 풀어보자!

1. 트리의 정보를 입력받는다.
2. 루트에서 리프노드로 bottom-up 탐색을 한다.
3. 결과 값을 출력한다.

 

🔎 DP수행 과정을 자세히 살펴보자!

 

🙋‍♀️ 먼저 트리DP 방식을 이해해보자. 예제 1번을 사용해보자!

 

그래프로 표현하면 다음과 같다.

 

1번 노드에서 끝 자리수에 따라 만들 수 있는 경우의 수는 다음과 같다. (1번 하나 뽑는것)

0	1	2	3	4	5	6	7	8	9
	1

 

2번 노드에서 끝 자리수에 따라 만들 수 있는 경우의 수는 다음과 같다.

0	1	2	3	4	5	6	7	8	9
	1 -> 3

- 우선 1번 하나 뽑는 1이라는 경우의 수가 있었다.

- 여기에 2를 하나 뽑는 경우 하나를 더해준다.

- 이전에 경우의 수에서 0번 이상 나타나는 끝자리 수는 1이다. 1에 현재 노드를 이어 붙일 수 있는지(오름차순이 성립되는지) 확인해 보니 붙일 수 있다. 그러므로 끝자리 수가 1인 경우 뒤에 1을 또 붙여준다.

 

3번 노드에서 끝 자리수에 따라 만들 수 있는 경우의 수는 다음과 같다.

0	1	2	3	4	5	6	7	8	9
	3	4

- 이전의 경우의 수에서 0번 이상 나타나는 끝자리 수는 1이며 3개의 경우의 수가 존재했다.

- 이때 3번 노드의 숫자는 2이고 1보다 크므로 뒤에 이어붙일 수 있다. 모든 1의 경우의 수에 이어붙일 수 있으므로 1의 경우의 수 만큼 누적하여 더해준다. 이때 끝자리 수는 2가 되므로 2에 추가해 준다. (0 -> 3)

- 3번을 하나 뽑는 경우를 더해준다. (3 -> 4) 

 

4번 노드에서 끝 자리수에 따라 만들 수 있는 경우의 수는 다음과 같다.

0	1	2	3	4	5	6	7	8	9
	3	4 -> 12

- 이전의 경우에서 0번 이상 나타나는 끝자리 수는 1과 2이다.

- 1은 3개의 경우의 수가 존재하며, 이 뒤에 4번 노드의 숫자인 2를 붙여줄 수 있으므로 1번 경우의 수만큼 누적하여 더해준다. (4 -> 7)

- 2는 4개의 경우의 수가 존재하며, 이 뒤에 4번 노드의 숫자인 2를 붙여줄 수 있다. 같은 방법으로 모두 붙여주어 누적하여 더해준다. (7 -> 11)

- 4번을 하나 뽑는 경우를 더해준다. (11 -> 12)

 

탐색이 끝난 후 모든 끝자리수에 따라 나타날 수 있는 경우의 수의 합을 구해준다. (3 + 12 = 15)

 

 

🔎 매 순간의 경우의 수를 모두 구해보면 다음과 같다.

 

[1번일 때]

1

 

[2번일 때]

1 (1번의 1)

11 (1번의 1 + 2번의 1)

1 (2번의 1)

 

[3번일 때]

12

112

12

1

11

1

2

 

[4번일 때]

122 (1번의 1 + 3번의 2 + 4번의 2)

1122

122 (2번의 1 + 3번의 2 + 4번의 2)

12

112

12

22

12

112

12

1

11

1

2 (3번의 2)

2 (4번의 2)

 

이전 값에 뒤에 오름차순으로 현재 숫자를 붙여줄 수 있다면 누적하여 더해준다는 의미가 어떤 의미인지 알 수 있을 것이다. 이제 문제로 돌아오자!

 

 

🔹 루트에서 리프노드 방향으로 탐색을 시작한다.

- 탐색은 한 방향으로만 이루어 져야 한다.

 

🔹 DFS 탐색을 한다.

- 먼저, 자기 자신을 뽑는 경우를 더해준다.

- 방문하지 않은 자식 노드로 탐색을 진행한다. (끝에 도달할 때 까지 탐색한다.)

- 더 이상 갈 수 있는 노드가 없다면 다시 부모로 되돌아와 결과를 합쳐준다.

- 이때 자식 노드의 탐색 결과 중에서 현재 노드(부모)의 값보다 크거나 같은 숫자가 있다면 오름차순이 성립한다.

- 성립하므로 모든 경우의 수를 현재 노드의 숫자에 해당하는 결과 배열에 누적하여 더해준다.

 

📌 이때 bottom-up 방식이라 조금 헷갈릴 수 있다!

- 기본 로직은 동일하고, 누적해서 더해주는 과정을 자식 노드가 아닌 부모 노드에 누적하여 더해주는 것이다.

 

🔹 결과값을 출력한다.

- 결과는 반환 배열에 누적되어 저장되어있다. 

- 배열의 모든 수를 더해주면, 답이 된다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int MOD = 1000000007;
    static int[] node_value;
    static ArrayList<Integer>[] edge;
    static boolean[] visited;
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        //입력
        int n = Integer.parseInt(bf.readLine());
 
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        node_value = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            node_value[i] = Integer.parseInt(st.nextToken());
        }
        if(n == 1) System.out.println("1");
 
        edge = new ArrayList[n + 1];
        for(int i = 1; i < n + 1; i++) {
            edge[i] = new ArrayList<>();
        }
        for(int i = 0; i < n - 1; i++) {
            String str2 = bf.readLine();
            StringTokenizer st2 = new StringTokenizer(str2);
            int n1 = Integer.parseInt(st2.nextToken());
            int n2 = Integer.parseInt(st2.nextToken());
            edge[n1].add(n2);
            edge[n2].add(n1);
        }
        //입력 끝
 
        visited = new boolean[n + 1];
        long[] result = dfs(1); //루트 -> 리프 탐색
 
        long total = 0;
        for(int i = 0; i < 10; i++) {
            total += result[i];
            total %= MOD;
        }
        System.out.println(total);
    }
 
    public static long[] dfs(int current) {
        visited[current] = true;
        long[] result = new long[10];
 
        result[node_value[current]] += 1; //자기 자신 뽑는 경우를 먼저 더해준다.
        for(int next : edge[current]) {
            if(visited[next]) continue; //이미 방문했던 노드는 방문하지 않는다.
 
            long[] next_result = dfs(next); //연결 노드를 방문한다. 
            for(int i = 0; i < 10; i++) { 
                result[i] += next_result[i]; //연결 노드의 방문 정보를 합쳐준다.
                if(i >= node_value[current]) result[node_value[current]] += next_result[i]; //오름차순이 성립된다면 모든 경우의 수를 더해준다.
                result[i] %= MOD; 
            }
        }   
        return result;
    }
}

 

관련 추천 문제

11057번: 오르막 수