백준 9489 : 사촌 (Python)

본문 링크

"""
딕셔너리를 통해서 간단하게 부모-자식 관계를 만든다.
이후 부모의 부모가 같은 노드들의 개수를 구한다
"""
import sys
input=sys.stdin.readline
from collections import defaultdict

while True:

    N,K=map(int,input().split())
    if [N,K]==[0,0]:
        break
    L=list(map(int,input().split()))
    Parent=defaultdict(int)

    index=0
    for i in range(1,N):
        Parent[L[i]]=L[index]
        if i<N-1 and L[i]+1<L[i+1]:
            index+=1

    count=0
    if Parent[Parent[K]]: # 부모의 부모가 존재한다면
        for Node in L:
            if (Parent[Parent[K]] == Parent[Parent[Node]]) and Parent[Node]!=Parent[K]: #부모의 부모가 같다면
                count+=1
    print(count)

📌 어떻게 접근할 것인가?

처음에 엄청 삽질을 한 문제이다. $Tree$ 를 입력받기 위해서 연속한 수끼리 부모-자식 관계가 되도록 배열도 3개씩 쓰고 겨우 구현했더니 사촌 노도를 찾는거에서 또 막혀버렸다.

다른사람의 풀이를 보니깐 굳이 복잡하게 생각할 필요도없고 리스트도 쓸 필요가없었다.

📌 from collections import defaultdict

파이썬에서 제공하는 강력한 라이브러리다.

Parent=defaultdict(int) 를 선언하고 부모-노드끼리 연결만해주면

이렇게 명확하게 알아서 만들어 준다. 부모-노드 관계가 복잡하면 그냥 이 라이브러를 쓰자.
다만 기본 값은 int 형으로 선언해주었다.
아무것도 선언하지않을시 error 가 발생할 수 있으니 주의하자.

📌 사촌 노드

사촌노드가 되는 조건은 어이없게도 간단했다.
두 노드가 부모노드가 다르면서 부모의 부모노드가 같다.
근데 이걸 딕셔너리를 활용하면 더 간단히 구현가능하다.

Parent[Parent[K]] == Parent[Parent[Node]]) and Parent[Node]!=Parent[K]

두 노드의 부모의 부모노드가 같고 부모노드가 서로 다른것을 이 한줄로 구현가능하다.

✅ 코드에서 주의해야할 점

• N,K 가 둘다 0 일때까지 계속 입력을 받아야한다.