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

문제

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

입력

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

출력

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

풀이

노드의 연결 정보를 입력받고 1을 루트노드로 설정했을 때 각 노드들의 부모노드를 출력해야한다.

이 문제를 dfs를 이용하여 해결했는데

우선 입력값을 matrix라는 2차원 리스트에 저장하고

1번부터 n번까지의 방문을 나타내기 위한 visit 리스트를 생성한다.

이제 루트 노드인 1부터 검사를 시작하여

각 노드들의 부모노드를 갱신시켜준다.

 

import sys
sys.setrecursionlimit(100000)
n = int(sys.stdin.readline().rstrip("\n"))
matrix=[[] for _ in range(n+1)]
visit=[0]*(n+1)
for i in range(n-1):
    start, end = map(int, sys.stdin.readline().rstrip("\n").split())
    matrix[start].append(end)
    matrix[end].append(start)

def dfs(start, matrix, visit):
    for i in matrix[start]:
        if(visit[i]==0):
            visit[i]=start
            dfs(i,matrix,visit)
dfs(1, matrix, visit)

for i in range(2,len(visit)):
    print(visit[i])