11725 트리의 부모 찾기

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline
sys.setrecursionlimit(10**9)
N = int(read())
tree = [[] for _ in range(N+1)]
parents = [0 for _ in range(N+1)]

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

def DFS(start,tree,parents):
    # start 노드에 연결된 vertex들을 확인하자.
    for i in tree[start]:
        if parents[i] == 0 : # visited의 역할도 겸해준다.
            parents[i] = start
            DFS(i,tree,parents)

DFS(1,tree,parents)

for j in range(2,N+1):
    print(parents[j])

3. 생각 및 풀이

생각

이 문제는 기본적인 트리문제이다. DFS를 잘 익혀야하므로 하루에 한번씩 이 문제에 대해 보고 지나가자.

문제 풀이

트리의 핵심인 DFS를 사용할줄 안다면, 쉽게 풀 수 있다. 자신과 연결된 노드를 graph에 잘 저장하고, parent를 visited처럼 활용하자.