등산 마니아( BOJ 20188 )

문제 : https://www.acmicpc.net/problem/20188

20188번: 등산 마니아

 

문제 파악하기

N개의 오두막과 (N-1)개의 오솔길로 이루어진 등산로가 주어질 때, 경로의 다양성을 구하는 문제입니다. 여기서 말하는 경로의 다양성이란 i번째 오두막에서 j번째 오두막으로 정산을 거쳐 이동할 때, 지나는 서로 다른 오솔길의 개수를 의미합니다. N개의 오두막 사이에 나올 수 있는 모든 경로의 다양성을 구해야하는데, 단순히 모든 경우의 수를 구하기에는 오두막의 개수가 300,000개이기 때문에 좀 더 효율적인 방법이 필요합니다.

 

문제 해결하기

우선 등산로의 모습에 초점을 맞춰봅시다. 등산로는 N개의 오두막과 오두막을 연결하는 (N-1)개의 오솔길로 이루어져 있습니다. 이 형태는 트리 형태와 동일하기에 우리는 오두막을 정점으로, 오솔길을 간선으로 생각하고 문제를 풀 수 있습니다. 단순히 두 오두막 사이의 간선의 개수라면 모든 오두막의 높이를 사용해서 구할 수 있지만, 이번 문제는 경로 상의 서로 다른 간선의 개수를 각각 구해야 합니다. 따라서 우리는 정점이 아닌, 간선에 초점을 맞춰서 문제를 풀어야 합니다.

 

각각의 간선이 사용되는 횟수를 말단 노드의 간선부터 차근차근 구해서 올라가면 우리는 모든 간선에 대해 사용되는 횟수를 구할 수 있습니다. 여기서 중요한 점은 어떻게 간선이 사용되는 횟수를 구할 수 있는지 입니다. [ A-B 간선 ]이 정점 A와 B를 연결하는 간선이며, A가 자식노드라고 가정해보겠습니다. [ A-B 간선 ]이 사용되는 경우 중 가장 먼저 생각할 수 있는 경우는 A의 자식들이 사용하는 경우입니다. A의 자식들은 항상 정산, 즉 루트를 거쳐야 합니다. 그렇기에 A의 자식노드들은 항상 [ A-B 간선 ]을 사용하게 됩니다. 다만, A의 자식이 여러 개라면 중복되는 경우를 제외한다는 점을 기억하세요. 예를 들어 A의 자식 AA와 AB는 서로의 경로를 구할 때 중복됩니다. 그렇기에 자식의 개수에 따라 중복되는 경우의 수를 제외해야 합니다. [ A-B 간선 ]이 사용되는 또다른 경우는 A가 자신의 자식 이외의 정점을 방문하는 경우 입니다. A는 항상 루트를 거쳐서 다른 정점으로 이동해야 하기 때문에 항상 [ A-B 간선 ]을 사용할 수 밖에 없습니다. 물론, A의 자식을 방문할 때에도 [ A-B 간선 ]을 사용해서 루트로 이동해야 하지만, 이 경우는 이미 A의 자식이 다른 노드를 방문하는 는 경우의 수를 사용하면 됩니다.

 

이렇게 각각의 간선을 자식 정점의 내용을 바탕으로 현재 정점의 가짓수를 구하는 알고리즘을 사용하면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define NMAX 300010
#define lint long long int
using namespace std;
 
int N, a, b;
vector< int > graph[NMAX];
 
int check[NMAX];
lint childCnt[NMAX];
vector< int > tree[NMAX];
 
lint ans;
lint dp[NMAX];
 
void makeTree(int idx) {
    for(int child:graph[idx]) {
        if(check[child]) continue;
 
        check[child] = 1;
        tree[idx].push_back(child);
        makeTree(child);
 
        childCnt[idx] += childCnt[child]+1;
    }
}
 
lint sv(int idx) {
    if(dp[idx] >= 0) return dp[idx];
    else {
        lint ret, checkChild;
 
        ret = checkChild = 0;
        for(int child:tree[idx]) {
            int tmp = checkChild*(childCnt[child]+1);
            ret += sv(child) - checkChild*(childCnt[child]+1);
 
            checkChild += childCnt[child]+1;
        }
        
        ret += N - (checkChild+1);
        
        if(idx != 1) ans += ret;
        return dp[idx] = ret;
    }
}
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<N;i++) {
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    check[1] = 1;
    makeTree(1);
 
    memset(dp, -1, sizeof(dp));
    sv(1);
    
    printf("%lld", ans);
 
}
 
/*
4
1 2
2 3 
3 4
ans: 14
*/

후기

처음에 다양성이라는 말이 헷갈렸지만 문제에서 트리라는 걸 직접적으로 알려주고 있기에 알고리즘을 어렵지 않게 세울 수 있는 문제였습니다. 다만, 자식 노드들의 값 중 중복되는 경우를 떠올리는데 조금 시간이 걸렸습니다. 트리에서 동적 프로그래밍을 연습하기에 적합한 문제라고 생각합니다.