DFS :트리의 부모 찾기(백준 11725번)

▶ 문제 : https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

##### 문제 #####
# 루트 없는 트리가 주어진다. 
# 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

##### 입력 #####
# 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 
# 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

##### 출력 #####
# 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

▶ 접근 방법

트리의 관계를 어떻게 표현할지가 관건이었다.
우선, 전체 노드 간의 관계를 담는 리스트를 하나 만들고,
각 노드 별 부모 노드를 표시할 리스트를 하나 더 만들어서 문제를 해결하였다.

 

▶ 풀이 코드

import sys

# 전체 노드의 개수를 입력받는다.
num_of_node = int(sys.stdin.readline().rstrip())

# 트리 정보를 담기 위한 리스트를 만든다.
tree_info = [[] for _ in range(num_of_node+1)]

# 부모 정보를 담기 위한 리스트를 만든다.
parent = [[] for _ in range(num_of_node + 1)]

# 트리 정보 리스트에 노드 간 관계를 입력한다.
for _ in range(num_of_node - 1):
    node_1, node_2 = map(int, sys.stdin.readline().split())
    tree_info[node_1].append(node_2)
    tree_info[node_2].append(node_1)


def DFS(tree_info, start, parent):
    # 시작 노드를 스택에 넣어준다.
    stack = [start]
    
    while stack:
        node = stack.pop()
        # 시작 노드와 인접한 노드들을 하나 씩 확인한다.
        for adj_node in tree_info[node]:
            # 인접 노드를 인덱스로 갖는 부모 정보 리스트에 시작 노드를 넣어준다.
            parent[adj_node].append(node)
            stack.append(adj_node)
            # 인접 노드를 인덱스로 갖는 트리 정보 리스트에서 시작 노드를 삭제한다.
            tree_info[adj_node].remove(node)
    return parent

# 2번 노드부터 순서대로 출력한다.
for i in list(DFS(tree_info, 1, parent))[2:]:
    print(i[0])

 

▶ 관련 링크

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.18 - [알고리즘] - 트리(Tree)란?