2644.촌수계산 - python

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

dfs
부모가 1명만 있는 구조

 

형제끼리는 촌수가 더해지지 않고 위아래로만 더해지니까 이진 트리에서 한 부모 밑에 2마리까지의 길이의 합과 같음

최소 조상부터 위에는 모두 동일한 조상이기 때문에 그 조상들은 다 제거한다

이진트리 구조이기 때문에 그냥 한 단계씩 위로 올라가면서 마주치는 조상들을 각각 리스트에 넣어놓고
2마리의 같은 조상은 다 제거하면 남은 리스트의 길이의 합이 촌수이다

d={}
input()
s,e=map(int,input().split())
n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    d[b]=a
    
def f(x,t):
    if d.get(x):
        return f(d[x],t+[x])
    return t+[x]
    
s1=set(f(s,[]))
e1=set(f(e,[]))

p=s1&e1
if p:
    s1-=p
    e1-=p
    print(len(e1)+len(s1))
else:
    print(-1)