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

[BanApp]

pypy3

import sys
sys.setrecursionlimit(100000)

n = int(sys.stdin.readline())
tree = [[] for _ in range(n+1)]
p = [0 for _ in range(n+1)]

def dfs(s,a,p):
    for i in tree[s]:
        if p[i] == 0:
            p[i] = s
            dfs(i,tree,p)

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

dfs(1,tree,p)

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

유명한 자료구조중에 하나인 트리구조이다. 근데 이건 사실 트리구조의 큰 개념만 이해하고 있으면 풀 수 있는 dfs 문제이다.
일단 tree의 인덱스값에 정점들의 값을 넣어준다. dfs로 p[I] == 0 은 방문한적이 없단 뜻이므로 해당 조건을 만족하면 p[I]에 s를 대입해서 방문 처리를 한다. 그럼 p[I]번째 값이 가지고 있는 s는 i번째 노드의 부모노드 값이 되는 것이다. 출력해주면 끝..!
아직은 난해한 tree.. 파이썬에서 트리구조 만들기 넘 귀찮..ㅠㅠ

[ghdcksgml1]

ㅋㅋㅋㅋ 트리의 부모도 찾아주시는 착한 분이시군요.

[BanApp]

트리의 부모가 왜 도망갔는지 알것 같은 문제였습니다.