[백준 11725] 트리의 부모 찾기 (python / 파이썬)

SILVER 2
https://www.acmicpc.net/problem/11725

풀이 아이디어) (풀기는 풀었는데..ㅜ 공부하려고 남겨두는 기록!)
① 처음에 연결된 노드를 x-y, y-x로 모두 등록한다.
② 1번 노드(루트 노드)부터 탐색을 시작한다. 이 때 1이 루트 노드이기 때문에 graph[1]에는 당연히 자식 노드만 있게 된다. 따라서 graph[1] 안에 있는 data(자식들)에 대해, result[data]를 1로 지정하고, graph[data] 에서 1을 제거한다. 그러면 graph[data] 에는 자식 노드들만 남게 된다.
③ data 에 대해 find_child 함수를 재귀적으로 실행한다.
④ 예제의 호출 방식은 1 -> 6 -> 3 -> 5 -> 4 -> 2 -> 7 식으로 진행된다.
⑤ 파이썬의 경우 리스트를 함수 안에서 호출하면 리스트 안의 값을 변경, 제거 등이 돼서 가능한 코드인 것 같다. (어? 이게 왜 되지? 느낌)

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def find_child(x):
    if graph[x] : # 자식 노드가 있을 때
        for data in graph[x]: # 자식에 대해
            result[data] = x # data의 부모는 x
            graph[data].remove(x) # graph[data] 에서 부모 x 삭제
            find_child(data)

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)

result = [0]*(N+1) # i의 부모는 result[i]

find_child(1)

for i in range(2, N+1):
    print(result[i])

풀이 공부)
나머진 모두 같고, parents[i] == 0 일 때 (방문 한 적 없을 때) DFS(깊이 우선 탐색) 으로 실행해준다는 지점만 다르다.

https://developmentdiary.tistory.com/435

import sys
sys.setrecursionlimit(10 ** 9)
 
N=int(sys.stdin.readline())#노드의 갯수
tree=[[] for _ in range(N+1)]
for _ in range(N-1):
    s,e=map(int,sys.stdin.readline().split())
    tree[s].append(e)
    tree[e].append(s)
 
#부모저장
parents=[0 for _ in range(N+1)]
 
def DFS(start,tree,parents):
    for i in tree[start]:#연결된 노드 모두탐색
        if parents[i]==0:#한번도 방문한적이 없다면
           parents[i]=start#부모노드 저장
           DFS(i,tree,parents)
 
 
DFS(1,tree,parents)
 
for i in range(2,N+1):
    print(parents[i])