-
[BOJ 1135, Python 3] 뉴스 전하기알고리즘/BOJ 2021. 8. 17. 21:48반응형
https://www.acmicpc.net/problem/1135
N이 작아서 풀이가 여러가지 풀이가 가능합니다.
제 풀이는 그리디 + 위상정렬입니다.
풀이
상사가 직속 부하한테 전화를 한다고 하니까 루트 노드(민식이)부터 시작하여 리프노드까지 전화를 돌린다고 합니다.
만약 직속 부하가 여러명이면 리프 노드까지 가는데 가장 오래 걸리는 순서대로 전화를 먼저하면 되겠습니다.
왜냐하면 만약 직속 부하가 3명이고 각각 직속 부하에서 리프 노드까지 가는데 [3분, 4분, 1분]이 걸린다고 해봅시다.
상사가 직속 부하한테 전화를 할 때 1분씩 걸리니 [4+1분, 3+2분, 1+3분]을 해야 모두에게 빠르게 소식을 전할 수 있는 5분이 나오기 때문입니다. 만약 1부터 시작하면 [1+1분, 3+2분, 4+3분]이라 빠르게 소식을 전해도 7분이라는 시간이 걸립니다.
위 풀이는 부모 노드가 자식 노드로 이동할 때 과정인데 저건 DP Top-down 풀이이고, 그리디는 리프 노드부터 시작하여 부모노드로만 계속 이동하게 만들면 됩니다.
부모노드는 자식 노드를 다 방문하고 나서야 건들 수 있다고만 설정하면 부모노드는 자기 자식들의 값을 다 확인하기 전까지 자신의 부모 노드에 영향을 주지 못하기 때문에 그리디로 풀 수 있게 됩니다.
자식 -> 부모로 이동하게 된다면 위와 같은 그림이 나오고, 이 문제를 위상정렬로 치환할 수 있습니다.
자식 노드를 전부 확인하여 부모 노드를 만질 수 있을 때, 부모 노드의 값은 풀이 첫 번째 문단에 설명하였으니 생략하겠습니다.
코드
123456789101112131415161718192021222324n = int(input())if n == 1:print(0); exit()arr = [*map(int, input().split())]val = [[] for _ in range(n)]up = [0] * nfor x in arr[1:]:up[x] += 1q = __import__('collections').deque()for i in range(1, len(arr)):if up[i] == 0:q.append([i, 0])while q:x, t = q.popleft()if x == 0: print(t)nx = arr[x]val[nx].append(t + 1)up[nx] -= 1if up[nx] == 0:val[nx].sort(reverse=True)nt = [val[nx][i] + i for i in range(len(val[nx]))]q.append([nx, max(nt)])cs 반응형'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ 4716, Python 3] 풍선 (1) 2021.08.18 [BOJ 9576, Python 3] 책 나눠주기 (0) 2021.08.17 [BOJ 17619, Python 3] 개구리 점프 (0) 2021.08.17 [BOJ 3109, Python 3] 빵집 (0) 2021.08.16 [BOJ 10775, Python 3] 공항 (0) 2021.08.16