이 문제에서는 n진 트리(n-ary tree)의 간선 정보가 담긴 2차원 배열이 주어지며, 이 배열을 이용해 만들어진 트리의 모든 리프 노드(leaf node)를 출력해야 합니다.
n진 트리란?
n진 트리는 각 노드가 최대 n개의 자식을 가질 수 있는 트리입니다. 즉, 하나의 노드는 1개, 2개, ... n개까지의 자식 노드를 가질 수 있습니다.
문제 예시
예제를 통해 문제를 자세히 살펴보겠습니다.
입력: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
출력: 1 4 7설명: 주어진 간선 배열로 트리를 구성하면 다음과 같은 구조가 됩니다.
이 트리의 리프 노드(자식이 없는 노드)는 1, 4, 7입니다.
접근 방법
이 문제는 DFS(깊이 우선 탐색)를 사용해 해결할 수 있습니다.
DFS로 트리를 순회하면 모든 서브트리의 리프 노드를 찾을 수 있습니다. 순회 과정에서 현재 노드에 자식 노드가 있는지 확인하고, 자식이 있는 경우(리프 노드가 아닌 경우)에는 플래그(flag) 값을 설정합니다. 마지막으로 플래그가 설정되지 않은, 즉 자식 노드가 없는 노드만 출력하면 됩니다.
여기서 한 가지 주의할 점은 부모 노드와의 간선도 인접 리스트에 포함되어 있으므로, 순회 시 부모 노드는 제외하고 처리해야 한다는 것입니다.
구현 코드
다음 프로그램은 위에서 설명한 해결 방법의 구현 예시입니다.
#include <bits/stdc++.h>
using namespace std;
void DFS(list<int> t[], int node, int parent) {
int flag = 0;
for (auto ir : t[node]) {
if (ir != parent) {
flag = 1;
DFS(t, ir, node);
}
}
if (flag == 0)
cout << node << "\t";
}
int main() {
list<int> t[1005];
pair<int, int> edges[] = {
{ 1, 2 },
{ 1, 3 },
{ 2, 4 },
{ 3, 5 },
{ 3, 6 },
{ 3, 7 },
{ 6, 8 }
};
int cnt = sizeof(edges) / sizeof(edges[0]);
int node = cnt + 1;
for (int i = 0; i < cnt; i++) {
t[edges[i].first].push_back(edges[i].second);
t[edges[i].second].push_back(edges[i].first);
}
cout << "Leaf nodes of the tree are:\n";
DFS(t, 1, 0);
return 0;
}실행 결과
Leaf nodes of the tree are: 4 5 8 7
코드 설명
- 간선 배열 처리: 주어진 간선들을 인접 리스트(adjacency list) 형태로 저장하여 양방향 그래프처럼 구성합니다.
- DFS 함수: 현재 노드의 모든 인접 노드를 확인하되, 부모 노드는 건너뜁니다. 자식 노드가 하나라도 존재하면 플래그를 1로 설정합니다.
- 리프 노드 판별: 재귀 호출이 끝난 후 플래그가 여전히 0이라면 해당 노드는 자식이 없는 리프 노드이므로 출력합니다.
이 알고리즘의 시간 복잡도는 O(V + E)이며, 여기서 V는 노드 수, E는 간선 수입니다. 트리의 모든 노드를 한 번씩만 방문하기 때문에 효율적인 방법입니다.