[백준] 11725번 - 트리의 부모 (파이썬)

문제) 백준 - 트리 (Tree) - 트리의 부모

-> www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

트리 상에서 연결된 두 정점을 인접 리스트 방식으로 나타낸다. 문제에서 트리의 루트가 1번으로 주어졌으므로 dfs를 이용해 1번부터 시작해 노드에 연결된  노드들을 순회한다. parent 리스트에 부모를 채킹(Checking)하면서, 0일 겨우 방문하지 않은 노드로 인식해 부모 노드로 저장한다.

 

 

 

소스 코드)

import sys
sys.setrecursionlimit(10 ** 8)

n = int(input())

tree = [[] for _ in range(n + 1)]

#부모 저장
parent = [0 for _ in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def dfs(tree, s, parent):

    #시작 노드부터 인접한 노드들 탐색
    for i in tree[s]:

        #만약 방문하지 않은 노드라면
        if parent[i] == 0:
            
            #부모노드로 저장
            parent[i] = s
            dfs(tree, i, parent)

dfs(tree, 1, parent)

for i in range(2, n + 1):
    print(parent[i])

Ps) 트리 문제 감 잡아가는중...