99클럽 코테 스터디 12일차 TIL, 백준 / 1135 / 뉴스 전하기

🔑 오늘의 학습 키워드 : 트리

🔗 문제링크 https://www.acmicpc.net/problem/1135

 

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

def dfs(node):
    # 리프 노드인 경우
    if not tree[node]:  
        return 0
    times = []
    for child in tree[node]:
        times.append(dfs(child))
    # 많은 시간을 요하는 것부터 처리
    times.sort(reverse=True)  
    max_time = 0

    for idx, time in enumerate(times):
        max_time = max(max_time, time + idx + 1)
    return max_time

input = sys.stdin.readline
N = int(input().strip())
people = list(map(int, input().strip().split()))

tree = defaultdict(list)
for idx in range(1, N):
    tree[people[idx]].append(idx)

print(dfs(0))

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

우선 트리 문제라고 생각했다.

 

그리고 트리문제는 bfs보다는 dfs가 훨씬 더 간결한 코드를 작성할 수 있다.

 

트리를 만들고 dfs로 순회하면서 계산하며 가장 최악의 시간을 갖는 사원의 최대값을 반환하면 될 것 같았다.

 

 

⏰ 예상 시간 복잡도 O(N + NlogN )

제한 사항

N은 50보다 작거나 같은 자연수이다.

😎 알고리즘 개요

1. 트리 생성

2. DFS 함수

• 리프 노드인 경우 0을 return
• 각 노드에 대해 하위 노드들의 전달 시간을 리스트에 추가한 후, 내림차순으로 정렬하여 가장 오래 걸리는 부하부터 처리
• 전달 시간 중 가장 큰 값을 return

3. 최종 결과 출력:

• 루트 노드(0번 직원)부터 DFS 탐색 후 최종 결과를 출력

 

✅ 오늘의 회고

 

- 재귀는 어렵다

 

- N과 M많이 풀어야겠다

 

- 트리는 dfs

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL