[백준 19535] ㄷㄷㄷㅈ

문제 링크 => 19535번: ㄷㄷㄷㅈ (acmicpc.net)

19535번: ㄷㄷㄷㅈ

---

트리를 활용한 경우의 수를 구하는 문제이다.

 

일단 G-Tree 를 구하는건 굉장히 쉽다.

 

현재 노드에서 이어져 있는 노드가 3개 이상인 경우 즉, n(n>=3)개로 이어져 있는 경우 G-Tree의 갯수는 nC3 = (n)(n-1)(n-2) / 3! 개이다.

 

그래서 모든 G-Tree를 구할 때 모든 노드를 방문하면서 n>=3 인 경우 nC3을 더해주면 그만이다.

 

문제는 D-Tree 이다.

 

parent 노드와 child 노드를 잡으면서 동시에 두 노드가 연결되어 있는것은 분명하므로 D-Tree의 갯수는 (parent 노드에서 child 노드를 제외한 연결된 노드의 갯수) * (child 노드에서 parent 노드를 제외한 연결된 노드의 갯수) 를 해주면 된다.

 

parent, child 노드를 잡는 과정은 Tree의 최상단 parent 노드(연결된 노드가 단 1개)를 잡도록 하여 parent 노드와 연결된 임의의 child 노드를 Queue에 push 하고 child 노드와 연결된 next 노드에 대해서 방문하지 않은 경우 Queue에 child 노드와 next 노드를 push 하여 모든 Tree를 방문하도록 하면 된다.

 

마지막으로 값을 비교할 때 int형으로 하기엔 값이 굉장히 커서 통과하지 못하므로 long long 을 사용하도록 한다.

 

풀이 code

---

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

vector<int> v[300001];
int n;
bool visited[300001];

void init() {
	for (int i = 1; i <= 300000; i++) visited[i] = false;
}

ll funcD(int x) {
	init();
	queue<pair<int, int>> q;
	q.push({ x,v[x][0] }); // 부모, 자식
	ll result = 0;
	visited[x] = true, visited[v[x][0]] = true;

	while (!q.empty()) {
		int parent = q.front().first;
		int child = q.front().second;
		result += (ll)(v[parent].size() - 1) * (ll)(v[child].size() - 1);
		q.pop();

		for (int i = 0; i < v[child].size(); i++) {
			int next = v[child][i];
			if (!visited[next]) {
				visited[next] = true;
				q.push({ child,next });
			}
		}
	}

	return result;
}

ll funcG(int x) {
	init();
	queue<int> q;
	q.push(x);
	visited[x] = true;
	ll result = 0;
	
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (v[x].size() >= 3) {
			ll combi = (v[x].size() * (v[x].size() - 1) * (v[x].size() - 2)) / 6;
			result += combi;
		}
		for (int i = 0; i < v[x].size(); i++) {
			if (!visited[v[x][i]]) {
				visited[v[x][i]] = true;
				q.push(v[x][i]);
			}
		}
	}

	return result;
}

int findParent() {
	queue<int> q;
	q.push(1);
	visited[1] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (v[x].size() == 1) return x;
		for (int i = 0; i < v[x].size(); i++) {
			int next = v[x][i];
			if (!visited[next]) {
				visited[next] = true;
				q.push(next);
			}
		}
	}
}

void solve() {
	int start = findParent();
	ll d = funcD(start);
	ll g = funcG(start);
	if (d > 3 * g) cout << "D";
	else if (d < 3 * g) cout << "G";
	else cout << "DUDUDUNGA";
}

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

	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

	solve();

	return 0;
}