백준 1135. 뉴스 전하기

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

1135번: 뉴스 전하기

def dfs(node, graph):
    if not graph[node]: # 자식 노드가 없는 경우
        return 0
    # 직속 상사의 모든 직속 부하에 대한 거리를 저장
    times = [dfs(child, graph) for child in graph[node]] # 모든 직속 부하들에 대해 반복
    times.sort(reverse=True) # 가장 먼 직속부하가 가장 앞에 오도록 정렬

    max_time = 0
    for i, time in enumerate(times):
        max_time = max(max_time, i + 1 + time) # 현재노드와 사장사이의 거리(+1) 최댓값 갱신

    return max_time # 모든 노드 간 거리 중 가장 긴 거리가 정답임!! = 노드와 사장 사이의 최대 거리

n = int(input())
graph = [[] for _ in range(n)]

for i, num in enumerate(map(int, input().split())):
    if num != -1:
        graph[num].append(i)

print(dfs(0, graph))

- 그리디 문제답게 보이면 쉽게 풀리는 문제였을 것 같다...

- 복잡하게 생각하지 말고 사장과 가장 멀리 있는 부하의 거리를 구하면 되는 문제 -> 발상의 전환! 단순하게 생각

- 나는 처음에 dp에 인덱스별로 집어넣고 하나씩 지우며 카운트해가는 걸 생각했는데 동시처리가 안돼서 fail

- gpt의 도움을 받아 겨우 이해했다...