Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 세그먼트 트리
- Python
- 브루트포스
- 그래프
- 투 포인터
- 이분 탐색
- 구현
- 애드 혹
- 플로이드-워셜
- 정렬
- 13164
- 싸피
- BFS
- 정수론
- 누적 합
- 수학
- 문자열
- 슬라이딩 윈도우
- 에라토스테네스의 체
- boj
- DFS
- 2357
- 그리디
- 모던 JavaScript 튜토리얼
- DP
- 트리
- SSAFY
- 맵
- JavaScript
- 해시 테이블
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 1135 - 뉴스 전하기 (Python) 본문
아이디어
DFS로 말단 직원에서부터 자신의 부하들에게 전화하는 데 걸리는 가장 긴 시간을 DP로 구해 나간다.
풀이
상사 번호를 리스트 P에 저장하고, 부하 직원의 번호를 상사 번호에 맞게 2차원 리스트 child에 저장한다.
함수 dfs에서는 자식 노드들을 탐색하여 구한 자식 노드에서 가장 오래 걸리는 시간을 빈 리스트 temp에 추가한다.
내림차순 정렬한 temp의 각 요소들과 그 순번을 더한 값 중 최댓값을 해당 노드에서 가장 오래 걸리는 시간으로 저장한다.
리프 노드에서는 자식 노드가 없어 temp가 빈 리스트이므로 for문과 if문 진입 없이 함수가 종료된다.
0번 직원부터 함수 dfs를 호출한 후 0번 직원의 dp 테이블에 저장된 결과값을 출력한다.
def dfs(idx):
temp = []
for i in child[idx]:
dfs(i)
temp.append(dp[i])
if temp:
temp.sort(reverse=True)
time = [temp[i]+i+1 for i in range(len(temp))]
dp[idx] = max(time)
N = int(input())
child = [[] for _ in range(N)]
P = list(map(int, input().split()))
for i in range(1, N):
child[P[i]].append(i)
dp = [0]*N
dfs(0)
print(dp[0])
'알고리즘' 카테고리의 다른 글
[BOJ] 13506 - 카멜레온 부분 문자열 (Python) (0) | 2023.02.01 |
---|---|
[BOJ] 2503 - 숫자 야구 (Python, JavaScript) (0) | 2023.02.01 |
[BOJ] 18312 - 시각 (Python, JavaScript) (0) | 2023.01.31 |
[BOJ] 2213 - 트리의 독립집합 (Python) (1) | 2023.01.29 |
[BOJ] 1949 - 우수 마을 (Python) (0) | 2023.01.29 |
Comments