[BOJ / Python] 11725번: 트리의 부모 찾기

문제: BOJ 11725번

풀이

각 노드의 부모를 구하는 프로그램을 작성하란다.
부모를 구하기엔 DFS가 맞는것 같아서 DFS를 사용하였다.
DFS로 탐색을 하며 바로 하위 노드들의 방문처리용 배열에 자신의 노드 번호를 넣어준다면 모두의 부모를 구할 수 있다.

최종코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = [[] for i in range(n + 1)]
vis = [0] * (n + 1)
for i in range(n - 1):		#인접리스트로 저장
    x, y = map(int, input().split())
    a[x].append(y)	
    a[y].append(x)


def dfs(x):
    for i in a[x]:		
        if vis[i] == 0:
            vis[i] = x		#방문하지 않은 자식들의 방문처리용 리스트에 자신의 값 부여
            dfs(i)


dfs(1)
for i in range(2, n + 1):		# 첫번째는 루트니까 두번째부터 출력
        print(vis[i])