문제

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

입력

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

출력

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

풀이

트리의 기본 형태
s,e 형태로 들어오는 노드들을 기록한 뒤
1번 루트 노드부터 밑으로 끝까지 내려가면서
새로운 트리에 자식위치에 부모노드를 기록했다.

import sys
sys.stdin = open('input.txt')
sys.setrecursionlimit(10**6)
input =sys.stdin.readline

N= int(input())
graph = [[]for _ in range(N+1)]

# 트리입력 받는 법
# 트리 갯수만큼 빈칸을 만들고 s,e방향 맞춰서 넣어주기
for _ in range(N-1):    # 모든 입력 받기
    s,e = map(int,input().split())
    graph[s].append(e)
    graph[e].append(s)

tree = [[]for _ in range(N+1)] # 부모노드 찾는 트리
visited =[0]*(N+1)             # 간 곳은 안가게 만들어
                               # 순환하지 않게 하기

def dfs(n):                     # 최상단 노드인 1에서 시작해서
                                # 트리가 내려간다
    visited[n]=1                # 현재 위치 방문처리 해주고

    for i in graph[n]:         # 그 위치에서 내려가는 값 모든값이
        if visited[i]==0:       # 방문을 안했다면
            tree[i].append(n)   # 트리 추가해주기 (자식에서 부모로 올라가는값)
            dfs(i)              # dfs 들어가기

dfs(1)
for t in tree:
    if t:
        print(*t)

추가

• 재귀가 깊어서 recursion에러가 날 때, 사용하는 함수
  sys.setrecursionlimit(10**6)
• 입력이 10만개씩 받을때 시간을 엄청 줄여줄 수 있다.
  input =sys.stdin.readline