문제 링크

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

문제 설명

• 족보가 그래프로 주어짐(부모2, 자식1)
• 왕위 계승을 주장하는 사람 리스트가 주어짐
• 나라를 세운 사람의 피를 가장 많이 받은 사람 출력

풀이

• 자식을 부모노드 부모를 자식노드로 하는 이진트리를 만듦
• 점화식을 세워서 재귀
  • 자신의 혈통 = (부모1의 혈통 + 부모2의 혈통) / 2
  • 나라를 세웠을 경우 1 리턴
  • 아닐 경우 0 리턴

코드

import sys


def init():
    ipt = sys.stdin.readline
    n, m = map(int, ipt().split())
    king = ipt().rstrip()
    adj_dict = dict()
    for _ in range(n):
        c, p1, p2 = ipt().split()
        for name in [c, p1, p2]:
            if name not in adj_dict:
                adj_dict[name] = []
        adj_dict[c] = [p1, p2]
    candidates = [ipt().rstrip() for _ in range(m)]
    return candidates, adj_dict, king


def dfs(curr):
    if curr == king:
        return 1
    if curr not in adj_dict:
        return 0
    if not adj_dict[curr]:
        return 0
    return (dfs(adj_dict[curr][0]) + dfs(adj_dict[curr][1])) / 2


candidates, adj_dict, king = init()
max_blood = float('-inf')
max_name = None
for name in candidates:
    blood = dfs(name)
    if blood > max_blood:
        max_blood = blood
        max_name = name
print(max_name)