#143 백준 파이썬 [11725] 트리의 부모 찾기

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

 

#Solution

https://claude-u.tistory.com/180참고하였음.

시간 초과가 너무 나서 찾는 데 한참 걸렸다. (if node not in visited:) 라는 함수는 O(n)의 시간 복잡도를 가지고 있는데, 편하다고 그냥 막썼다. 리스트 내부 탐색은 훨씬 더 효율적인 함수들을 써주는 것으로 하자.

 

- 결국 트리를 그래프 형태로 구현해서 부모 노드를 찾는 방식으로 진행하였다.

- 다만 그래프처럼 순회하지 않고, 한 방향으로만 쭉쭉 내려가므로 visited 리스트는 제거해 주었다.

- bfs, dfs 어느 것을 사용해도 무방하다.

 

import sys

node = int(input())
node_graph = [[] for _ in range(node + 1)]
parent = [[] for _ in range(node + 1)]

#트리를 그래프 형태로 생성

for _ in range(node - 1):
    i, j = map(int, sys.stdin.readline().split())
    node_graph[i].append(j)
    node_graph[j].append(i)

#DFS나 BFS나 무관

def dfs(graph_list, start, parent):
    stack = [start]
    
    while stack:
        node = stack.pop()
        for i in graph_list[node]:
            parent[i].append(node)
            stack.append(i)
            graph_list[i].remove(node)
    return parent

for i in list(dfs(node_graph, 1, parent))[2:]:
    print(i[0])