🔑 오늘의 학습 키워드 : 트리
🔗 문제링크 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
'Coding test' 카테고리의 다른 글
99클럽 코테 스터디 14일차 TIL, 프로그래머스 / 징검다리 (0) | 2024.08.04 |
---|---|
99클럽 코테 스터디 13일차 TIL, 프로그래머스 / 입국심사 (0) | 2024.08.03 |
99클럽 코테 스터디 11일차 TIL, 프로그래머스 / 가장 큰 수 (0) | 2024.08.01 |
99클럽 코테 스터디 10일차 TIL, 백준 / 11279 / 최대힙 (0) | 2024.07.31 |
99클럽 코테 스터디 9일차 TIL, 백준 / 1927 / 최소 힙 (0) | 2024.07.30 |