알고리즘 스터디 - 백준 11725번 : 트리의 부모 찾기

문제 해석

• 루트 없는 트리인데 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성
• 첫째 줄에 노드의 개수 N (2 <= N <= 100,000)
• 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어짐
• 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력

코드

import sys
sys.setrecursionlimit(10**9)

N = int(input())

# 그래프의 연결을 포함하는 그래프 생성
graph = [[] for _ in range(N+1)]

for _ in range(N-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# 그래프의 방문된 노드를 추적하는 세트
visited = set()
# 부모 코드 집어넣기
parent = [0 for _ in range(N+1)]

# DFS 함수
def dfs(node):
    # 조합에 방문한 노드를 집어넣는다.
    visited.add(node)        
    for neighbour in graph[node]:
        if neighbour not in visited:
            parent[neighbour] = node
            dfs(neighbour)

# 함수를 실행
dfs(1)
for i in range(2, N+1):
    print(parent[i])

• 말이 안되게 오래 걸렸는데 C++ 20ms 보고 현타왔다.