[파이썬 | BOJ | 19535] ㄷㄷㄷㅈ

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

19535번: ㄷㄷㄷㅈ

 

문제

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

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

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

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

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

입력

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

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

출력

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

풀이

일단 간선의 개수가 30만개 이므로 O(n^2)의 꼴이 되면 약 구백억이 되어 시간초과가 발생하게 된다.

따라서 모든 간선을 한번만 돌면서 D-트리와 G-트리를 구분해야 한다.

D-트리는 어떤 간선을 기준으로 봤을때, 양쪽의 노드에서 degree값이 2이상일때 성립한다. 왜냐하면 어떤 간선이 있을때 양쪽의 노드의 degree가 1이면 결국 현재 간선밖에 없다는 소리이므로, 이 간선이 D-트리의 중심 간선이 될 수 없다는 뜻이기 때문이다.

 

따라서 수식으로 표현하면 어떤 간선이 Node-R, Node-L을 연결하는 간선이라면 (degree[R]-1)*(degree[L]-1) 값이 D-트리의 개수가 되고, 모든 간선을 탐색하면 D-트리의 개수를 셀 수 있다.

 

G-트리는, 노드를 기준으로 탐색했을때, 어떤 노드의 degree가 3이상이면, combination(degree, 3)연산을 수행하면 된다. 이때 degree가 최대 29만 9999까지 될 수 있다. 따라서 팩토리얼로 계산해서도 안되고, 파스칼 삼각형을 이용한 재귀적인 방법으로도 컴파일 오류가 나기때문에, 그냥 일반적으로 인간이 수학적으로 조합식을 계산하는 방식으로 함수를 구성해서 풀었다.