문제

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

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

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

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

입력

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

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

출력

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

문제 링크

My solution (Python)

import sys

N = int(sys.stdin.readline())
linkArr = [0] * N
edges = []
# 링크 수를 arr에 담고, edges를 채운다.
for _ in range(N - 1):
    a, b = map(int, sys.stdin.readline().split(" "))
    linkArr[a - 1] += 1
    linkArr[b - 1] += 1
    edges.append([a, b])
resD, resJ = 0, 0
# 조합을 이용하여 ㅈ트리를 구한다.
for i in range(N):
    resJ += linkArr[i] * (linkArr[i] - 1) * (linkArr[i] - 2) / 6 if linkArr[i] >= 3 else 0
# 두 노드의 link 수를 이용하여 ㄷ트리를 구한다.
for a, b in edges:
    resD += (linkArr[a - 1] - 1) * (linkArr[b - 1] - 1)
if resD > resJ * 3:
    print("D")
elif resD < resJ * 3:
    print("G")
else:
    print("DUDUDUNGA")

My logic & Feedback

처음에 DFS로 풀었더니 시간초과가 났다.

그 이유는, ㄷ트리를 구할 때 단순히 link되어있는 노드의 for문을 돌려서 재귀를 한 번 더 돌았기 때문이다…

생각해보니, DFS로 ㄷ트리를 구하면 중복 탐색의 수가 많아지므로, 무조건 시간초과가 날 수 밖에 없을 것 같았다.

그래서 무조건 O(N)으로 풀어야 함을 깨닫고, 다른 방법을 생각했다.

그리고 BFS로 겨우겨우 풀었는데,

또 다시 생각해보니, ㄷ트리와 ㅈ 트리 모두 ‘트리 자체의 연결 구조’는 사실 별로 신경쓰지 않아도 되고,

단지 각 노드의 degrees만 알면 ㅈ트리는 조합으로, ㄷ트리는 두 노드의 degrees의 곱으로 바로 구할 수 있는 것이었다!

결국 O(N)으로 답을 도출해 낼 수 있었다.

이런 류의 그래프 문제를 많이 풀다보니 그래프 문제가 나오면 무조건 연결관계 구조를 만들어내는 습관이 있는데,

문제가 요구하는 것이 무엇인지 명확하게 분석하고 나서 풀이 전략을 세우는 연습이 필요할 것 같다.

아니면 나처럼 먼 길을 돌아가게 된다…