[백준] 11725번 > 트리의 부모 찾기

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

문제

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

입력

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

출력

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

예제 입력 1

7

1 6

6 3

3 5

4 1

2 4

4 7

예제 출력 1

4

6

1

3

1

4

예제 입력 2 복사

12

1 2

1 3

2 4

3 5

3 6

4 7

4 8

5 9

5 10

6 11

6 12

예제 출력 2 복사

1

1

2

3

3

4

4

5

5

6

6

 

---

풀이

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])

dfs로 트리를 그래프 형식으로 구현하였다.