[백준] 1135번 : 뉴스전하기

1135번: 뉴스 전하기

1135번: 뉴스 전하기

🤔 문제분석

깊이우선탐색, 다이나믹프로그래밍 문제의 유형으로 지금까지 접하지 못했던 문제의 유형이다.

최상위노드로부터 리프노드까지 방문한뒤에 자기자신의 값을 갱신하는 깊이우선탐색 방식으로 문제를 해결하였다. 탐색을 해가면서 해당 노드는 자기자신의 자식노드로부터 가장 오래 걸린 시간을 갱신해나아간다. 여기서 자기자신의 자식노드들을 리스트에 담아내고 리스트에 담기전에 자기자신의 자식노드는 걸리는시간이 계산이 되어야한다. 담아낸 리스트로부터 가장 오래걸리는 자식노드로 순서로 방문을 해가면서 갱신한다.

 

정리를 하자면 아래와 같다.

1. 자식노드를 노드를 방문한다.
2. 리프노드인경우 자기자신을 0으로 초기화한다.
3. 자식노드가 있는경우 자식노드중에서 가장 오래걸리는 노드를 기준으로 내림차순 정렬한다.
4. 정렬을 순회하면서 하나씩 방문해나아간다. ( cnt 값을 1씩 증가시켜가면서 )
5. 그중에 가장 오래걸리는 값을 자기자신의 값으로 갱신한다.

💻 코드

import sys

input = sys.stdin.readline

N = int(input())
emp = list(map(int, input().split()))
node = [[] for _ in range(N)]
child_cnt = [0 for _ in range(N)]

def solve(x):
    global child_cnt
    child_node = []
    if len(node[x]) == 0:
        child_cnt[x] = 0
    else:
        for child in node[x]:
            solve(child)
            child_node.append(child_cnt[child])

        child_node.sort(reverse=True)
        child_node = [child_node[i] + i + 1 for i in range(len(child_node))]
        child_cnt[x] = max(child_node)

for i in range(1, len(emp)):
    node[emp[i]].append(i)

solve(0)
print(child_cnt[0])

🎯 피드백 및 개선사항

새로운 유형의 문제를 접할 수 있어서 좋았습니다. 정렬, 다이나믹프로그래밍, 깊이우선탐색을 종합적으로 활용하는 응용력을 얻었습니다.