백준 15805 : 트리 나라 관광 가이드 (Python)

본문 링크

import sys
input=sys.stdin.readline


N=int(input())
L=list(map(int,input().split()))

visit=set()
visit.add(L[0])
dp=[0]*(200001)
dp[L[0]]=-1

for i in range(1,N):
    if L[i] not in visit:
        dp[L[i]]=L[i-1]
        visit.add(L[i])

print(len(visit))
for i in range(len(visit)):
    print(dp[i] , end=" ")

📌 어떻게 접근할 것인가?

트리를 순회한 결과를 통해서 부모를 찾는 문제입니다. 잘 보면 한번도 방문하지 않은 지점은
이전의 노드가 바로 부모노드입니다.

따라서 $set$ 을 사용하여 중복처리를 합니다. 만약 처음방문하는 지점이라면
$dp$ 배열에다가 이전ㅇ 인덱스 값을 넣어줍니다.

이후 중복이 없는 $set$ 의 길이를 출력하고 그 길이만큼 $dp$ 값을 출력해줍니다.

✅ 코드에서 주의해야할 점

• 반복문을 돌기 전에 $dp[L[0]]=-1$ 과 $visit.add(L[0])$ 을 해줍니다.