19535번: ㄷㄷㄷㅈ

문제 설명

https://www.acmicpc.net/problem/19535

19535번: ㄷㄷㄷㅈ

[문제]

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

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

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

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

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

 

[입력]

 첫 번째 줄에 트리의 정점 수 N이 주어진다. (4 ≤ N ≤ 300000)

두 번째 줄부터 N−1개의 줄에 트리의 각 간선이 잇는 두 정점의 번호 u, v가 주어진다. (1 ≤ u, v ≤ N)

 

[출력]

첫 번째 줄에 주어진 트리가 D-트리라면 D, G-트리라면 G, DUDUDUNGA-트리라면 DUDUDUNGA를 출력한다.

 

[예제 입력 1]

4
1 2
2 3
3 4

[예제 출력 1]

D

[예제 입력 2]

4
1 2
1 3
1 4

[예제 출력 2]

G

[예제 입력 3]

6
1 2
2 3
3 4
4 5
4 6

[예제 출력 3]

DUDUDUNGA

---

풀이

 이 문제의 경우 노드 4개를 먼저 정하고 이들의 노드 연결을 파악하는 건 매우 복잡하고 어렵기 때문에, 문제를 조금 더 쉽게 해결하기 위해서는 이미 연결되어 있는 노드들에 추가적으로 관계를 파악해서 트리 구조를 확인해야 한다.

 예를 들어 구조가 간단한 'ㅈ'모양 트리의 경우, 하나의 노드를 중심으로 3개의 노드가 연결되어 있다. 이를 알고리즘에 적용하면 특정 트리의 노드에서 해당 노드와 연결된 노드의 개수가 3개 이상이면 'ㅈ'모양 트리가 무조건 있다는 뜻이다. 게다가 이들의 모든 경우의 수를 구할 때도, 조합(nC3)을 이용하면 매우 간단하게 풀어낼 수 있다.

 추가로 'ㄷ'모양 트리는 약간 복잡한데, 일단 하나의 노드를 기준으로 연결되어 있는 2개의 노드를 택한다. 이후 연결된 노드 중 하나에서 해당 노드의 연결된 노드를 택하면 'ㄷ'모양 노드가 될 수 있다. 이를 경우의 수 계산에 적용하면, 특정 노드 한 개에서 노드 2개를 택하는 경우의 수(순열)에 그 중 하나의 노드에 연결된 다른 노드들의 개수(특정 노드 제외)를 곱하면 하나의 노드에서 주어지는 'ㄷ'모양 트리의 개수를 구할 수 있다. 물론 이 방법은 하나의 트리가 2번 중복되기 때문에 해당 계산이 모두 끝나고 총 경우의 수를 2로 나눠주면 된다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> treeInfor[300001];

int main() {
	int N, u, v;
	long long D = 0;
	long long G = 0;

	cin >> N;

	for (int i = 1; i < N; i++) {
		cin >> u >> v;
		treeInfor[u].push_back(v);
		treeInfor[v].push_back(u);
	}

	for (int i = 1; i <= N; i++) {//트리 파악
		long long childNum = treeInfor[i].size();
		if (childNum >= 2) {
			for (int j = 0; j < childNum; j++) {//ㄷ트리 파악
				D += (childNum - 1) * (treeInfor[treeInfor[i][j]].size() - 1);
			}
			if (childNum >= 3) {//ㅈ트리 파악
				G += childNum * (childNum - 1) * (childNum - 2) / 6;
			}
		}
	}

	D /= 2;//ㄷ트리의 경우 중복 제거

	if (D > G * 3)
		cout << "D" << endl;
	else if (D < G * 3)
		cout << "G" << endl;
	else
		cout << "DUDUDUNGA" << endl;

	return 0;
}

---

결과