[Python/파이썬] 백준 19535번 ㄷㄷㄷㅈ

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

코드

from math import comb

n = int(input())
children = [0]*(n+1)
graph = []
for _ in range(n-1):
    u, v = map(int, input().split())
    children[u] += 1
    children[v] += 1
    graph.append((u, v))

d_num, g_num = 0, 0
# ㄷ
for u, v in graph:
    d_num += (children[u]-1)*(children[v]-1)

# ㅈ
for i in range(1, n+1):
    if children[i] >= 3:
        g_num += comb(children[i], 3)

if d_num > g_num*3:
    print("D")
elif d_num < g_num*3:
    print("G")
else:
    print("DUDUDUNGA")

 

문제를 처음 봤을 때, "ㅈ"은 한 노드에 다른 노드가 3개 연결된 경우를 구하면 되니까 쉬웠는데, "ㄷ"은 어떻게 할까 생각을 많이 했다.

 

트리도 결국 그래프의 일종이니까 BFS를 사용해볼까 생각도 해봤지만, 최대 30만개가 넘는 노드에 각각 BFS를 통해 ㄷ자를 찾는 것은 비효율적이고 반복 연산이 너무 많을 것 같았다.

 

그래서 구글링을 통해 풀이를 살짝 찾아 봤더니 노드에서 다른 노드를 탐색하는 것이 아니라 처음에 입력받은 간선 정보들을 이용하여 풀 수 있다는 것을 알았다.

 

코드 설명

1. 각 노드에 인접한 노드의 개수를 저장하는 배열 children과 간선 정보를 저장할 배열 graph를 만든다.
2. 간선정보를 입력받으며 children과 graph에 알맞게 정보를 넣어준다.
3. ㄷ의 개수 구하기
   • 간선에 포함된 노드들에 인접한 노드의 개수에서 1을 뺀 값을 곱한다. 1을 빼는 이유는 현재 선택된 간선에 포함된 노드의 연결 정보는 제외시키기 위해서다.
   • 모든 간선 정보에 대해 위 과정을 통해 곱한 값들의 합을 구하면 ㄷ자 트리의 전체 개수를 구할 수 있다.
4. ㅈ의 개수 구하기
   • ㅈ은 한 노드에 3개의 인접 노드가 있는 것을 찾으면 되므로 구하기 쉽다. 우리는 처음에 간선을 입력받을 때, 각 노드에 인접한 노드들의 개수를 children 배열에 저장해두었다. ㅈ은 그 간선들 중 무작위 3개만 고르면 되므로 $_nC_3(n은 현재 노드에 인접한 노드의 개수)$을 하면 현재 노드에서 만들 수 있는 ㅈ의 개수를 구할 수 있다.
5. 3과 4의 과정으로 D-트리와 G-트리의 개수를 각각 구했으므로 이것을 갖고 문제의 조건에 맞는 문자를 출력해준다.

 

문제와 해결

위 코드로는 PyPy3를 사용했을 때만 통과가 된다. 파이썬도 통과되게 하려면 시간 최적화가 더 필요할 것 같다...

 

처음에는 $_nC_3$을 구할 때, math 모듈의 factorial을 사용하여 $\frac{n!}{(n-3)!3!}$으로 구했었는데, 이렇게 하면 PyPy3로도 시간 초과가 발생했다. 그 이유는 사실 잘 모르겠어서 chatGPT한테 물어봤다.

이 코드가 더 빠르게 실행되는 이유는 comb 함수를 사용하기 때문입니다. comb 함수는 Python의 내장 함수로, 최적화된 알고리즘을 사용하여 조합을 계산합니다. 이전 코드에서 사용된 factorial 함수를 사용한 조합 계산 방식은 비효율적이며, 특히 큰 수에 대해 성능이 떨어집니다.

자세히 설명하자면:
comb 함수 사용: comb 함수는 Python의 표준 라이브러리인 math 모듈에 포함되어 있으며, 조합 계산을 효율적으로 처리합니다.이는 내부적으로 최적화된 알고리즘을 사용하므로, 직접 factorial 함수를 사용하여 계산하는 것보다 빠릅니다.

불필요한 연산 제거:이전 코드에서 factorial을 직접 계산할 때 불필요한 중간 값들이 많이 계산됩니다. 예를 들어, factorial(a)를 계산하고, 다시 factorial(b)와 factorial(a - b)를 계산하는 방식은 반복적인 연산이 포함되어 있습니다.반면에, comb 함수는 이러한 불필요한 연산을 피하고 필요한 값만 바로 계산합니다.

 

가장 핵심적인 내용은 "comb 함수는 내부적으로 최적화된 알고리즘을 사용하기 때문에 직접 factorial 함수를 사용하여 계산하는 것보다 빠르다"는 것이다. 역시 내장모듈에 내부적으로 구현된 함수들이 대부분의 경우에 가장 빠른 실행 속도를 보이는 것 같다. 사실 이번에 comb 함수는 처음 알게 되었는데 나중에 필요할 때 또 사용해봐야겠다.