[코드트리] 트리의 부모노드

https://www.codetree.ai/missions/9/problems/parent-node-of-the-tree?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 

루트 노드가 1인 트리에서 각 노드의 부모 노드를 구하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 노드의 개수 n이 주어집니다.

두 번째 줄 부터 n 번째 까지 트리 상에서 연결된 두 정점이 주어집니다.

• 1 ≤ n ≤ 100,000

출력 형식

한 줄에 하나씩 2번 노드부터 n번 노드까지 각 노드의 부모 노드 번호를 순서대로 출력합니다.

 

입출력 예제

예제1

입력:

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

 

출력:

1
1
2
3
3
4
4
5
5
6
6

 

---

import sys
sys.stdin=open('input.txt', 'r')

# 트리 순회를 진행합니다. # DFS 방식으로 진행하며, # 진행되는 간선에 대해 (부모, 자식) 관계를 정의해줍니다.
def DFS(x):                 # 부모는 x, 자식이 y가 됩니다.
    visited[x]=1
    for y in graph[x]:
        if visited[y]==0:       # 아직 방문해본적이 없는 노드라면 # 트리의 부모-자식 관계가 결정됩니다.
            visited[y]=1
            parent[y]=x         # y의 부모는 x 
            DFS(y)              # 다음 y의 자식들을 살펴본다

if __name__=="__main__":
    n=int(input())
    graph = [[] for _ in range(n+1)]
    
    for _ in range(n-1):                # n - 1개의 간선 정보를 입력받습니다.
        a,b=map(int, input().split())
        graph[b].append(a)
        graph[a].append(b)
    
    visited = [0]*(n+1)
    parent = [0]*(n+1)
    DFS(1)                      # 1번부터 트리 순회를 진행합니다.
    
    # 부모 노드를 출력합니다.
    for i in range(2,n+1):
        print(parent[i])