노드가 n개인 루트가 있는 일반 트리가 있다고 가정해 보겠습니다. 노드는 0부터 n-1까지 번호가 매겨져 있으며, 각 노드에는 소문자 영어 알파벳 하나로 이루어진 레이블이 붙어 있습니다. 레이블은 labels 배열로 입력되며, labels[i]는 i번째 노드의 레이블을 담고 있습니다. 트리는 간선 목록으로 표현되는데, 각 간선 e의 [u, v]는 u가 부모이고 v가 자식임을 의미합니다.
우리가 구해야 할 것은 크기가 n인 배열 A입니다. 여기서 A[i]에는 i번째 노드와 같은 레이블을 가진 노드 중에서 i번째 노드의 하위 트리(subtree)에 속한 노드의 개수가 저장됩니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
이때 n = 5이고 label = "ccaca"입니다.
그러면 출력은 [3, 2, 1, 1, 1]이 됩니다. 루트(0번 노드)는 같은 레이블을 가진 세 개의 자손을 포함하고 있고, 1번 노드는 두 개의 자손을 가지며, 나머지 노드들은 자기 자신만 해당 레이블을 만족하기 때문입니다.
풀이 접근 방법
이 문제는 깊이 우선 탐색(DFS)을 후위 순회(post-order) 방식으로 수행하면 효율적으로 해결할 수 있습니다. 각 노드를 방문할 때 자식 노드들의 레이블 빈도 정보를 먼저 모은 뒤, 자신의 레이블을 추가하고 결과 배열에 기록하는 방식입니다. 구체적인 단계는 다음과 같습니다.
- E := 주어진 간선 목록으로 그래프(인접 리스트)를 생성합니다.
- N := 각 노드 번호와 대응하는 레이블을 담은 맵을 만듭니다.
- R := 크기가 n이고 0으로 초기화된 결과 리스트를 준비합니다.
- r(ni) 함수를 정의합니다.
- C := 레이블별 빈도수를 저장할 맵(Counter)을 생성합니다.
- E[ni]에 있는 각 이웃 e에 대해 다음을 수행합니다.
- E[e]에서 ni를 제거하여 부모 방향으로의 재방문을 막습니다.
- 재귀 호출한 r(e)의 결과를 C에 반영합니다.
- 현재 노드의 레이블 N[ni]를 C에 반영합니다.
- R[ni] := C[N[ni]]로 현재 노드의 답을 기록합니다.
- C를 반환합니다.
- 메인에서 r(0)을 호출하여 루트부터 탐색을 시작합니다.
- 최종적으로 R을 반환합니다.
각 노드마다 최대 26개의 알파벳 빈도만 관리하면 되므로 전체 시간 복잡도는 O(n × 26)으로 매우 효율적입니다.
구현 예제
아래 Python 구현을 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict, Counter
def solve(n, edges, labels):
E = defaultdict(set)
for f, t in edges:
E[f].add(t)
E[t].add(f)
N = {i: e for i, e in enumerate(labels)}
R = [0] * n
def r(ni):
C = Counter()
for e in E[ni]:
E[e].remove(ni)
C.update(r(e))
C.update((N[ni]))
R[ni] = C[N[ni]]
return C
r(0)
return R
n = 5
edges = [[0,1],[0,2],[1,3],[0,4]]
labels = "ccaca"
print(solve(n, edges, labels))
입력
5, [[0,1],[0,2],[1,3],[0,4]], "ccaca"
출력
[3, 2, 1, 1, 1]