11725

날짜 : 2022. 11. 21

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10 ** 9)

n = int(sys.stdin.readline())
parent = [0] * (n + 1)
tree = [[] for i in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)


def dfs(start):  # start : 부모노드
    for i in tree[start]:
        if parent[i] == 0: # 부모관계 설정
            parent[i] = start
            dfs(i)


dfs(1) # 1부터 시작(root)
for i in range(2, n+1):
    print(parent[i])

 

 

풀이

- DFS를 활용한 문제

- BFS를 활용해서 풀어보려 했지만 시간초과가 발생했다.

- 처음 root 노드는 주어지기 때문에 1을 기점으로 DFS를 시작하면서 진행한다

 

 

알게된 점

- 

 

 

참고 사이트

-