전공/백준
11725
yha97
2022. 11. 21. 20:05
날짜 : 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를 시작하면서 진행한다
알게된 점
-
참고 사이트
-