https://www.acmicpc.net/problem/19535
분류 : 트리, 그리디, 조합
연합동아리 면접 준비때문에 바쁜 한주를 보냈다. 그래서 저번주는 쉬운 문제들로 골라서 올릴 만한 내용이 없었다.(핑계)
이번주는 난이도를 올려서 재밌는 문제들이 많았고, 하나를 소개해 보겠다.
접근 방법
먼저 중요한 점은 정점이 30만개라는 것이다.
DFS,BFS로 트리를 단 한번만 순회하면서 정답을 찾아야 한다.
나는 원래 트리 문제에서 incidence_li[][]와 parent[]를 사용하여 인접(자식)노드의 리스트, 부모 노드를 저장한다. 다만 이 문제에서는 O(N^2)이상의 시간 복잡도를 사용하면 안되므로, incidence_li[][]를 사용할 필요가 없이 개수로 무언가를 해결해야 한다고 느꼈다.
전체 탐색
이런 문제를 많이 풀어보면 알겠지만, 노드 번호가 오름차순으로 입력이 들어오지도 않고, 루트 노드가 1로 고정되어 있지도 않다. 그러므로 특정 노드를 기준으로 삼아서 부모-자식 관계를 정립해야 한다.
ㅈ 트리
ㅈ모양의 트리는 아이디어가 쉽게 떠오른다. 한 정점에 3개의 노드가 연결되어 있는 모양이므로, 탐색을 하며 자식 노드들중 3개의 노드를 고르는 경우를 고르면 된다.
ㄷ 트리
ㄷ모양의 트리를 어떻게 처리할 지 참 어려웠다. 이런 문제에서 내가 잘 쓰는 아이디어가 있는데, 다음과 같다.
부모노드 -> 자식노드 탐색은 O(N)이다.
자식노드 -> 부모노드 탐색은 O(1)이다.
라는 아이디어에 기반하여, 모든 노드에 대해 노드->부모 노드-> 조부모 노드 이런식으로 탐색하려고 했지만,
오른쪽 그림의 경우를 생각하지 못했고, 자식 노드를 탐색하게 되면 결국 O(N^2)가 되어 TLE를 받는다.
결구 힌트를 좀 봤는데, 풀이가 참 신선했다.
지금까지 나는 정점을 기준으로 모든 트리문제를 풀었던 것 같은데, 이 문제에서는 간선을 기준으로 접근하는 방법으로 풀 수 있었다.
ㄷ모양의 트리에서 가운데 간선을 기준으로, 인접 노드의 개수-1를 서로 곱해주는 방식으로 할 수 있었다.
입력을 받을 때 간선의 정보들을 리스트에 저장을 해 놓고, 정점마다 인접 노드의 개수 카운트한다.
풀이
import math
import itertools
import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())
incidence_li = list([] for _ in range(N + 1))
parent_li = [-1] * (N + 1)
child_cnt = [0] * (N + 1)
edge_li = []
cntD, cntG = 0, 0
for _ in range(N - 1):
u, v = map(int, sys.stdin.readline().split())
incidence_li[v].append(u)
incidence_li[u].append(v)
edge_li.append([u, v])
def solveG(n):
cnt_children = len(incidence_li[n])
return math.comb(cnt_children, 3)
# ㅈ
for i in range(1, N + 1):
cntG += solveG(i)
# ㄷ
for edge in edge_li:
u, v = edge
cntD += (len(incidence_li[u]) - 1) * (len(incidence_li[v]) - 1)
if cntD > cntG * 3:
print("D")
elif cntD < cntG * 3:
print("G")
else:
print("DUDUDUNGA")ㅈ트리는 부모-자식 관계가 필요한데, ㄷ 트리는 간선의 정보를 바탕으로 푼다는 방식이 매우 참신했다. 따봉~
