[PS] 백준 #19535. ㄷㄷㄷㅈ

문제 정보

• 난이도: 골드 III
• 문제 주소: https://www.acmicpc.net/problem/19535
• 이 문제를 푼 이유: 알고리즘 스터디 - 트리, dp

 

문제

어느 날, 트리를 물끄러미 보고 있던 동현이는 엄청난 사실을 하나 발견했다. 바로 정점이 네 개인 트리는 ‘ㄷ’과 ‘ㅈ’의 두 종류밖에 없다는 사실이다!

정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고 하자.

이제, 동현이는 세상의 모든 트리를 다음과 같은 세 종류로 나누었다.

• D-트리 : ‘ㄷ’이 ‘ㅈ’의 $3$배보다 많은 트리
• G-트리 : ‘ㄷ’이 ‘ㅈ’의 $3$배보다 적은 트리
• DUDUDUNGA-트리 : ‘ㄷ’이 ‘ㅈ’의 정확히 $3$배만큼 있는 트리

신이 난 동현이는 트리만 보이면 그 트리에 있는 ‘ㄷ’과 ‘ㅈ’이 몇 개인지 세고 다니기 시작했다. 하지만 곧 정점이 $30$만 개나 있는 트리가 동현이 앞에 나타났고, 동현이는 그만 정신을 잃고 말았다. 동현이를 대신해 주어진 트리가 D-트리인지 G-트리인지 아니면 DUDUDUNGA-트리인지 알려주자!

 

나의 풀이

ㄷ 트리와 ㅈ 트리를 어떻게 구분해야 할지는 곧바로 생각나지 않았다. 그래서 구글링을 통해 힌트를 참고하였다.

• ㄷ 트리: 하나의 엣지에 연결된 두 정점에 대하여 각 정점별로 연결된 다른 정점의 개수가 각각 1개 이상씩이면 ㄷ 트리에 해당한다. 즉, A - B 가 연결되었을 때, (A와 연결된 정점들의 개수 - 1) * (B와 연결된 정점들의 개수 - 1) 의 값이 1 이상이면 ㄷ 트리에 해당된다. 
• ㅈ 트리: 하나의 정점에 대하여 연결된 다른 정점이 3개 이상이면 ㅈ 트리에 해당한다.  

따라서 ㄷ 트리를 구분하기 위해서는 Edge Set이 필요하고, ㅈ 트리를 구분하기 위해서는 각 정점별로 연결된 정점을 저장하는 adj 배열이 필요하다.

1. 이차원 배열 adj에 그래프 정보를 저장한다. 이 때 Edge Set 'E' 에 각 엣지들을 저장해둔다. 엣지는 pair 자료구조로, 시작점과 종점을 저장하고 있다.
2. E에서 엣지들을 하나씩 꺼내보면서 ㄷ 트리의 개수를 구한다. 이 때 엣지에 연결된 두 정점 A, B에 대하여 (A와 연결된 정점들의 개수 - 1) * (B와 연결된 정점들의 개수 - 1) 의 값만큼을 더하면 된다. (양의 정수일 때만)
3. 모든 정점들을 돌면서 각 정점에 연결된 다른 정점들의 개수를 구하고, 3 이상일 경우 nC3 을 계산하여 ㅈ 트리의 개수를 구한다. Combination 함수는 dp를 이용하여 간단하게 구현하였다. 
4. ㄷ 트리의 개수와 ㅈ 트리의 개수의 3배를 비교하여 알맞게 출력한다.

#include <bits/stdc++.h>

using namespace std;

vector<vector<long long>> adj;
vector<pair<long long, long long>> E;

long long int dp[300001][4]{ 0, };
int N;

long long int combination(int n, int r) {
    // base case
    if (n == 1 || r == 0 || r == n) return 1;

    // memoization
    if (dp[n][r] != 0) return dp[n][r];

    long long int result = combination(n - 1, r - 1) + combination(n - 1, r);
    dp[n][r] = result;
    return result;
}


int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    long long d = 0, g = 0;
    adj.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        long long u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        E.push_back(make_pair(u, v));
    }

    // ㄷ Tree: E에서 하나씩 꺼내보고 엣지에 연결된 두 정점과 연결된 정점들의 개수 구하기
    for (auto& edge : E) {
        long long D = (adj[edge.first].size() - 1) * (adj[edge.second].size() - 1);
        if (D > 0) d += D;
    }

    // ㅈ Tree: 한 정점에 연결된 엣지가 3개 이상이면 그 중 3개 뽑기
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() >= 3) {
            g += combination(adj[i].size(), 3);
        }
    }

   // cout << "D: " << d << " / G: " << g << endl;
    if (d > g * 3) cout << "D";
    else if (d == g * 3) cout << "DUDUDUNGA";
    else cout << "G";

    return 0;
}