067 트리의 부모 찾기

첫번째 코드

 

DFS를 이용해서 부모 노드를 answer 리스트에 저장해 가는 방법을 이용하여 코드를 작성한다.

뭔가 tree를 다룬 문제의 느낌이라기 보다는 DFS 문제를 다루는 느낌이다.

 

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

n = int(input())
tree = [[] for _ in range(n+1)]
visited = [False] * (n+1)
answer = [0] * (n+1)

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

def DFS(x):
    visited[x] = True
    for i in tree[x]:
        if not visited[i]:
            answer[i] = x
            DFS(i)

DFS(1)

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

 

DFS와 많이 친해지고 있는 기분!

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/11725.%E2%80%85%ED%8A%B8%EB%A6%AC%EC%9D%98%E2%80%85%EB%B6%80%EB%AA%A8%E2%80%85%EC%B0%BE%EA%B8%B0

programmers/백준/Silver/11725. 트리의 부모 찾기 at main · ornni/programmers