[백준][JAVA] BOJ 20188 등산 마니아

 

문제 읽기🤔

---

문제

동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오두막에서도 다른 모든 오두막으로 하나 이상의 오솔길을 따라 이동하는 것이 가능하다. 오두막들은 1번부터 N번까지 번호가 붙어 있으며, 1번 오두막이 산 정상에 있다. 1번 오두막에서 다른 오두막으로 가는 가장 짧은 길을 따라 가면서 거치는 모든 오솔길들은 항상 산을 내려가는 방향이다.

철수는 등산 마니아이다. 철수가 한 오두막에서 다른 오두막으로 갈 때는 항상 산 정상을 거치는 가장 짧은 길을 따라 간다. 이렇게 간 길의 다양성은 길에 포함된 오솔길의 개수로 정의된다. 두 번 이상 지나간 오솔길은 한 번만 센다는 것에 주의하라.

아래 그림은 가능한 하나의 상황을 보여 준다. 산 정상에 1번 오두막이 있고 3번 오두막과 4번 오두막이 오솔길로 이어져 있다.

아래 그림은 2번 오두막에서 7번 오두막으로 가는 가장 짧은 길을 보여준다.

아래 그림은 2번 오두막에서 7번 오두막으로, 정상을 거쳐서 가는 가장 짧은 길을 보여 준다.

등산로의 구성을 입력으로 받아 모든 가능한 i, j의 쌍에 대해서(1 ≤ i < j ≤ N), 철수가 i번 오두막에서 j번 오두막으로 가는 길의 다양성의 총 합을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 N이 주어진다. 다음 N −1개의 줄에 오두막 번호 두 개가 공백 하나를 사이에 두고 주어진다. 두 오두막이 오솔길로 이어져 있다는 뜻이다.

출력

첫 번째 줄에 문제의 정답을 출력한다.

제한

• 2 ≤ N ≤ 300 000

 

 

문제 풀이📝

---

트리 구조에서, 모든 노드의 쌍에 대한 다양성의 합을 구하는 문제이다.

여기서 다양성이란, 해당 노드에서 1번 노드(루트 노드)를 거쳐 목표 노드로 갈 때의 간선 개수의 합이다.

(주의할 점은, 이미 세었던 간선은 두 번 세지 않는 것이다!)

그러므로 (i, j)의 다양성과 (j, i)의 다양성은 같다.

 

도저히 아이디어가 떠오르지 않아서 다른 사람의 풀이를 참고했다.

https://velog.io/@qwerty1434/%EB%B0%B1%EC%A4%80-20188%EB%B2%88-%EB%93%B1%EC%82%B0-%EB%A7%88%EB%8B%88%EC%95%84

백준 20188번: 등산 마니아

 

1) LCA 알고리즘

대부분 LCA(최소공통조상) 알고리즘을 활용한 풀이를 생각할 수 있었을 것이다.

그러나 모든 쌍에 대한 경우를 고려하여야 하기 때문에 O(N^2 log N)의 시간복잡도를 가지게 되어

N의 범위를 고려한다면, 위의 문제를 해결하기에는 적합하지 않다.

 

2) 트리에서의 DP

관점의 전환이 필요하다.

노드를 중심으로 생각하여 선택한 노드 쌍의 다양성을 구하는 방식이 아닌

간선을 중심으로 해당 간선이 몇 번 이용되는지를 구하는 방식을 사용해야 한다.

 

i) 특정 간선의 아래에 있는 노드들은 반드시 그 간선을 지난다.

위와 같이 빨간색 간선 아래에 있는 노드들(5, 6, 7, 2, 8)을 포함하는 노드 쌍은 필연적으로 빨간색 간선을 지난다.

예를 들어 노드의 쌍이 (2, 6)으로 주어진다면, 2 -> 1 -> 6의 순서로 노드를 방문해야 하므로 빨간색 간선을 지나게 된다.

이러한 규칙이 성립하는 이유는 해당 노드에서 루트 노드인 1번 노드를 거쳐서 목표 노드로 가야한다는 조건 때문이다.

 

ii) 노드의 쌍 중, 한 노드만 특정 간선 아래에 있어도 해당 간선을 지난다.

만약 주어진 노드 쌍이 (2, 4)라고하자.

2번 노드 빨간색 간선 아래에 존재한다. 

결과적으로 2 -> 1 -> 4의 순서로 노드를 방문해야 하므로 빨간색 간선을 지나게 된다.

주어진 노드 쌍이 (4, 3)이라면 어떨까?

두 노드는 모두 빨간색 간선 아래에 존재하지 않는다.

그렇기 때문에 4 -> 1 -> 3의 순서로 노드를 방문할 때 빨간색 간선을 지나지 않는다.

 

iii) 결론

결과적으로 모든 쌍을 고려했을 때, 5, 6, 7, 2, 8번 노드들을 제외한 나머지 노드들(1, 4, 3)의 쌍은 빨간색 간선을 지나지 않는다. (5, 6, 7, 2, 8번 노드들은 5번 노드를 루트로 하는 서브트리에 속한 노드들이라고 할 수 있다)

나머지 노드들의 개수를 구하는 공식은 다음과 같다.

(나머지 노드의 개수) = (전체 노드의 개수) - (해당 간선아래에 있는 서브트리의 노드 개수)

그러므로 전체 노드 쌍 개수에서 나머지 노드들의 쌍 개수를 빼주면 빨간색 간선이 활용되는 횟수가 도출된다.

고로 모든 간선에 대하여 해당 간선이 활용되는 횟수를 구하여 모두 더해주면 된다.

 

 

구현🛠️

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main_20188 {

    static int N;
    static List<Integer>[] tree;
    static int[] subtree;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList[N + 1];
        subtree = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree[a].add(b);
            tree[b].add(a);
        }

        DFS(1, 1);
        long answer = 0;
        // 1번 노드는 루트노드이므로 고려대상이 아님
        for (int i = 2; i <= N; i++) {
            int X = N - subtree[i]; // X는 해당 간선 아래에 존재하지 않는 노드의 개수
            // 해당 간선을 활용하는 총 횟수 =
            // 전체 노드 쌍 개수 - 해당 간선 아래에 존재하지 않는 노드들의 쌍 개수
            answer += countNodePair(N) - countNodePair(X);
        }
        System.out.println(answer);
    }

    // nC2
    public static long countNodePair(int n) {
        return 1L * n * (n - 1) / 2;
    }

    // cur 노드를 루트로 하는 서브트리에 속한 노드의 개수를 구한다.
    public static int DFS(int cur, int parent) {
        subtree[cur] = 1;
        for (int child : tree[cur]) {
            if (child == parent) {
            	continue;
            }
            subtree[cur] += DFS(child, cur);
        }
        return subtree[cur];
    }
}

 

 

실행결과✅

---