[백준] 뉴스 전하기

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

1135번: 뉴스 전하기

문제를 제대로 파악하는데 시간이 걸린 문제입니다. 처음에는 단순 BFS로 접근했다가 부하 직원에게 동시에 통화가 불가능하다는 조건을 깨닫고는 풀이를 1차 변경, 간접 상사 직원도 통화가 가능하다고 생각했는데 직속 부하 직원에게만 통화가 가능하다고 해서 2차 풀이 변경, 무조건 현재 노드를 루트로 하는 서브트리의 노드 개수가 많은 노드부터 BFS로 탐색하는 풀이로 진행했다가 마지막으로 각각의 서브트리에서 통화하는데 걸리는 시간을 계산하여 상위 노드로 전달하는 방식으로 3차 풀이 변경을 통해 해결할 수 있었습니다.

 

풀이의 접근법은 다음과 같습니다. DFS로 트리를 탐색하면서 현재 노드의 각각의 자식 트리들에게 통화하는데 걸리는 시간을 리턴받아 리스트에 담아놓습니다. 그 다음 그 리스트를 내림차순으로 정렬하게 되면 자식 트리중에서 탐색이 오래 걸리는 순으로 정렬이 되게 됩니다. 동시에 전화가 불가능하기 때문에 전화하는데 오래 걸리는 트리부터 전화를 걸게 되면 각각 1, 2, 3 ... 분이 걸리게 되므로 해당 값을 더해줍니다. 마지막으로 해당 값들중 최대 값을 리턴해주면 되는데 이 값이 현재 노드를 루트로 하는 트리에 전화를 걸기 위해 필요한 시간이 되게 됩니다.

 

import sys
from collections import defaultdict

input = sys.stdin.readline

# 직원의 수
n = int(input())

# 각 직원의 직속 상사에 대한 정보
employees = list(map(int, input().split()))

graph = defaultdict(list)

# 트리 구축
for i in range(1, n):
    graph[employees[i]].append(i)

answer = 0

def dfs(cur):
    global answer
    # 자식 트리들중 가장 시간이 오래 걸리는 경우
    childs = []

    for next_employee in graph[cur]:
        childs.append(dfs(next_employee))

    start = 1
    # 시간이 오래 걸리는 순으로 내림차순 정렬
    childs.sort(key=lambda x: -x)

    # 시간이 오래 걸리는 자식 트리를 먼저 탐색하면서 순서에 따른 시간 추가
    for i in range(len(childs)):
        childs[i] += start
        start += 1
    # 자식이 없는 경우에는 0을 리턴하고 자식 중에 가장 탐색이 오래걸리는 시간을 리턴
    # 탐색이 오래걸리는 시간이 cur노드를 루트로 하는 서브트리에서 전화하는데 걸리는 시간이 된다.
    return 0 if not childs else max(childs)

answer = dfs(0)

print(answer)