백준 - 11725번 트리의 부모 찾기 python 문제풀이 [Hellfer]

 

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

11725번: 트리의 부모 찾기

🔷 알고리즘 분류 - 그래프 이론, 트리, 너비 우선 탐색

난이도 - 실버 2

트리는 계층적인 구조를 가지는 비선형 자료구조로, 노드(node)와 노드를 연결하는 간선(edge)으로 구성됩니다. 

 

트리는 루트 노드(root node), 부모 노드(parent node), 자식 노드(child node), 잎 노드(leaf node, 터미널 노드) 등으로 구성되며, 특정 노드의 하위 트리(sub-tree)를 구성하는 노드들은 해당 노드의 자손(descendant)이라고 합니다.

파이썬에서는 주로 딕셔너리와 리스트를 활용하여 트리를 구현합니다. 

 

예를 들어, 각 노드와 노드의 자식들을 딕셔너리의 키와 값으로 표현하는 방식으로 트리를 만들 수 있습니다. 

 

또한, 각 노드를 객체로 표현하고, 객체의 속성으로 부모 노드나 자식 노드를 참조하는 방식으로도 트리를 구현할 수 있습니다.

트리를 이용한 알고리즘에는 다양한 것들이 있습니다. 대표적으로는 다음과 같습니다:

1. 트리 순회(Tree Traversal): 트리의 모든 노드를 방문하는 방법입니다. 

 

깊이 우선 순회(DFS, Depth-First Search)와 너비 우선 순회(BFS, Breadth-First Search)가 있습니다.

2. 이진 탐색 트리(Binary Search Tree): 이진 탐색 트리는 왼쪽 자식 노드의 값이 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값이 부모 노드의 값보다 크다는 특성을 가지는 트리입니다. 

 

이를 통해 특정 값을 효율적으로 찾을 수 있습니다.

3. 힙(Heap): 힙은 각 노드의 값이 자식 노드의 값보다 크거나 작다는 특성을 가지는 트리입니다. 

 

최대 힙에서는 루트 노드의 값이 가장 크고, 최소 힙에서는 루트 노드의 값이 가장 작습니다. 힙은 우선순위 큐를 구현하는 데 주로 사용됩니다.

4. 트라이(Trie): 트라이는 문자열이나 연관 배열을 저장하는 데 사용되는 트리입니다. 

 

각 노드가 하나의 문자를 나타내고, 문자열의 끝을 표시하는 특별한 노드가 있습니다.

트리의 균형(Balanced Tree): 균형 트리는 트리의 모든 노드에서 왼쪽과 오른쪽 하위 트리의 높이 차이가 일정한 범위 이내인 트리를 말합니다. 

 

이를 통해 트리의 높이를 최소화하여 연산의 효율성을 극대화합니다. 대표적인 균형 트리로는 AVL 트리, 레드-블랙 트리 등이 있습니다.

🔶문제 풀이 - 너비우선탐색을 이용한 풀이

import sys
from collections import deque

# 너비 우선 탐색 함수
def bfs(start):
    queue = deque([start])  # 탐색을 시작할 노드를 큐에 넣습니다.
    while queue:  # 큐가 빌 때까지 탐색을 반복합니다.
        v = queue.popleft()  # 큐에서 노드를 하나 꺼냅니다.
        for i in tree[v]:  # 꺼낸 노드와 인접한 노드들을 확인합니다.
            if parent[i] == 0:  # 인접한 노드의 부모 노드가 아직 정해지지 않았다면,
                parent[i] = v  # 꺼낸 노드를 그 부모 노드로 정하고,
                queue.append(i)  # 인접한 노드를 큐에 넣습니다.

N = int(sys.stdin.readline())  # 노드의 개수를 입력받습니다.
tree = [[] for _ in range(N+1)]  # 각 노드와 그 노드에 인접한 노드들의 정보를 담을 리스트를 초기화합니다.
parent = [0 for _ in range(N+1)]  # 각 노드의 부모 노드를 담을 리스트를 초기화합니다.

# 트리의 간선 정보를 입력받아 인접 리스트를 만듭니다.
for _ in range(N-1):
    n1, n2 = map(int, sys.stdin.readline().split())
    tree[n1].append(n2)
    tree[n2].append(n1)

bfs(1)  # 1번 노드부터 너비 우선 탐색을 시작합니다.

# 각 노드의 부모 노드를 출력합니다.
for i in range(2, N+1):
    print(parent[i])

🔶문제 이해하기

다음과 같은 입력값이 주어졌다고 가정해 보겠습니다.

 

7
1 6
6 3
3 5
4 1
2 4
4 7

 

이 입력값은 다음과 같은 트리를 나타냅니다.

 

 1
 / \
6   4 - 2
|   |
3   7
|
5

 

각 줄의 두 숫자는 하나의 간선을 나타내며, 이 간선은 두 노드를 연결합니다. 

 

예를 들어, 첫 번째 줄의 '1 6'은 노드 1과 노드 6이 연결되어 있음을 나타냅니다.

이를 코드에 적용하면, 먼저 노드의 개수 7을 입력받고, 인접 리스트 tree와 부모 노드 리스트 parent를 초기화합니다. 

 

다음으로 간선 정보를 입력받아 인접 리스트를 만듭니다.

이후 bfs(1)을 호출하여 1번 노드부터 BFS를 시작합니다. 

 

이 함수는 큐에 시작 노드를 넣은 뒤, 큐가 빌 때까지 다음을 반복합니다.

 

큐에서 노드를 하나 꺼내고, 꺼낸 노드와 인접한 노드들 중 아직 부모 노드가 정해지지 않은 노드를 찾아 부모 노드를 설정하고, 해당 노드를 큐에 넣습니다.

마지막으로 2번 노드부터 7번 노드까지 각 노드의 부모 노드를 출력합니다. 

 

이 경우의 출력 결과는 다음과 같습니다.

 

4
6
1
3
1
4