Week 01 ~ 04 : 알고리즘 문제 풀이

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

정글러 2021. 11. 21. 01:58
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

n = int(input())
parent = [0 for i in range(n + 1)]
V = {}
for i in range(1, n + 1) :
    V[i] = []
for i in range(n-1) :
    v1, v2 = map(int, input().split())
    V[v1].append(v2)
    V[v2].append(v1)

def DFS(p) :
    for i in V[p] :
        if parent[i] == 0 :
            parent[i] = p
            DFS(i)

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

 

v1과 v2가 연결되어있다는건 인풋으로 알려주지만 방향은 알려주지 않을 때, 주어진 정보를 통해서 방향을 추론해 작성하는 문제이다.

 

루트 없는 트리에서 1이 루트라고 가정한다는게 무슨 헛소리인가 싶었지만, 아무튼 연결정보가 1개인 애는 막내이니 각각의 막내에서부터 거슬러 올라가며 부모리스트를 짜는 DFS를 짰다.

근데 시간초과가 나더라

 

여기서 시간을 줄일수 있을리가 없는데 이게 무슨소린가 싶어 검색해보니

루트 없는 트리인데 1이라는 루트를 정했으니 사실 루트가 있는 트리라고 한다(???)

아무튼 1이라는 루트가 있게 됐으니까 1과 연결된 점은 무조건 1의 자식이고, 이를 토대로 그냥 DFS를 1에 딱 한번만 써주면 된다고 한다.

 

무슨 문제가 이래...