백준 11725번: 트리의 부모 찾기 - 파이썬(DFS)

이 문제는 루트노드가 1로 가정하고 있으므로

2번부터 n-1번까지 순서대로 노드들의 부모노드를 찾아서 출력해주면 되는 문제이다.

 

탐색문제이므로 dfs,bfs 등 편한 알고리즘을 사용하면 될 것 같다.

나는 dfs알고리즘을 이용해서 풀어보았다.

 

우선 dfs알고리즘을 사용할 때는 재귀의 깊이를 늘려놓는 것이 편하다.

그리고 트리구조를 표현할 때 인접리스트(adjacent list)방식으로 표현했다.

인접리스트만으로는 부모와 자식노드의 관계를 알 수는 없다.

따라서 parent리스트를 따로 만들어서 순서대로 부모노드를 넣어주었다.

 

# 11725번: 트리의 부모 찾기
import sys
sys.setrecursionlimit(10**6)

n = int(input())
adj_list = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int,input().split())
    adj_list[a].append(b)
    adj_list[b].append(a)

parent = [0] * (n+1)

def dfs(curr_idx):
    for a in adj_list[curr_idx]:
        if visit[a] == True:
            continue
        else:
            parent[a] = curr_idx

        visit[a] = True
        dfs(a)

visit = [False] * (n+1)

visit[1] = True
dfs(1)

for i in range(2,n+1):
    print(parent)