L. Family Tree

-iknoom1107

문제 풀이

문제가 길어서 어려워보이지만 내용은 쉽고 구현이 귀찮은 문제입니다.

1. X에서 루트노드까지 올라가면서 X부터의 거리를 셉니다. -> s

2. Y에서 루트노드까지 올라가면서 Y부터의 거리를 셉니다. -> t

3. 최초의 공통 조상에서 s와 t의 값을 확인하여 X와 Y의 관계를 파악합니다.

이때 s가 t보다 큰 값이라고 가정하겠습니다.

1. t == 0

   s > 2 : (great-) * (s-2) grand-mother

   s > 1: grand-mother

   s==1: mother

2. t == 1

   s > 2 : (great-) * (s-2) grand-aunt

   s > 1: aunt

   s==1: SIBLINGS

3. t > 1

   COUSINS

만약 공통 조상을 가지지 않으면 NOT RELATED를 출력하면 됩니다.

소스코드

<Python>

N, X, Y = input().split()
N = int(N)
parent = {}

for _ in range(N):
    P, C = input().split()
    parent[C] = P

X_parent = {X : 0}
s = 0
p = X
while p in parent:
    s += 1
    p = parent[p]
    X_parent[p] = s

relation = ""

p = Y
t = 0
while True:
    if p in X_parent:
        s = X_parent[p]
        if s < t:
            t, s = s, t
            X, Y = Y, X
        if t == 0:
            if s > 2: relation += "great-" * (s - 2)
            if s > 1: relation += "grand-"
            relation += "mother"
        elif t == 1:
            if s == 1: relation = "SIBLINGS"
            if s > 2: relation += "great-" * (s - 2)
            if s > 1: relation += "aunt"
        else:
            relation = "COUSINS"
        break

    if p not in parent:
        break

    p = parent[p]
    t += 1

if not relation:
    relation = "NOT RELATED"

if relation in ["SIBLINGS", "COUSINS", "NOT RELATED"]:
    print(relation)
else:
    print(Y, "is the", relation, "of", X)