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

- 문제:

  - n개의 노드수를 입력하고 첫번째 1노드를 제외한 2~ n개의 부모노드를 순서대로 나열하는 문제.

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

- 풀이:

- 문제 해결 방식:  DFS,  재귀 함수

-> 일단 dfs/bfs의 개념부터 알아가느라 정답을 먼저 보고 고민을 해봤다. 문제는 이해가 갔는데 정답 코드를 봐도 왜 저렇게 배열을 만드는지 이해가 안간다.. (12.28) -> 이해 완료!

import pandas as pd
import sys

n = int(input())

tree = [[] for _ in range(n+1)] # 빈 배열 생성
parent = [-1]*(n+1)
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    
def dfs(n):
    for i in tree[n]:
        if parent[i] == -1:
            parent[i] = n
            dfs(i)
dfs(1)
for i in range(2, n+1):
    print(parent[i])

--> tree의 배열을 보면 이런식으로 결과가 나오는데 각 노드 순서별로 어떤 노드와 연결되어있는지 나타내는 배열이다!

예) 0번 노드는 공백, 1번 노드와 연결된 노드는 4,6, 2번 노드와  연결된 노드는 2, 3번 노드와 연결된 노드는 5,6

 

* 문제 해결법: dfs 문제의 트리 노드 문제는 아예 함수 공식을 외우자!