https://www.acmicpc.net/problem/14267
시간 2초, 메모리 512MB
input :
- n m (2 ≤ n, m ≤ 100,000)
- n명의 직속 상사의 번호 (직속 상사의 번호는 자신의 번호보다 작으며, 1번이 사장)
- i w (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)
output :
- 1번부터 n번의 직원까지 칭찬을 받은 정도를 출력
조건 :
- 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.
예재에서 "2 2"로 입력이 들어오게 되면 2, 3, 4 모두 2씩 칭찬을 받는다.
"5 6"의 경우에는 5만 6의 칭찬을 받게 되는 것이다.
가장 문제가 된 부분은 칭찬을 어떻게 계산할 것인지 였다.
-
입력 받을 떄 마다 계산
이렇게 한다면 해당 노드에서 leaf 노드까지 계속 계산을 해야 하는데 m개의 줄을 입력 받을 떄 이런 탐색을 계속 돈다면 시간이 부족할 거다. -
기록
문제를 해결한 이들이 추천하는 방식이다. 우선적으로 각 노드들의 칭찬을 기록한 후에 마지막에 BFS, DFS, 순회 등을 이용해서 다 더하는 방식이다.
문제의 조건에서 상사의 번호는 자신보다 작다고 하였기 떄문에 상사들은 부모 노드가 되게 된다. 결국 트리 구조를 가지고 있는 예제가 들어온다는 것이다.
그래서 graph와 같은 리스트를 만들어 해당 노드와 연결된 노드들을 저장한다.
root는 당연히 사장(1번 노드)로 생각하면 된다.
해당 노드를 만나게 된 경우 ans 리스트를 업데이트 하도록 하였다. 근데 생각해보니 q에다가 cost를 저장하지 말고 for문에서 ans[next_node] = ans[node] + value[next_node]와 같은 식을 사용해도 될 것 같다.
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
parent = [0] + list(map(int, sys.stdin.readline().split()))
ans, graph, value = [0] * (n + 1), [[] for _ in range(n + 1)], dict()
for i in range(2, n + 1):
graph[parent[i]].append(i)
for _ in range(m):
i, w = map(int, sys.stdin.readline().split())
if i not in value:
value[i] = w
else:
value[i] += w
q = deque([(0, 1)])
while q:
cost, node = q.popleft()
ans[node] = cost
for next_node in graph[node]:
temp = 0
if next_node in value:
temp += value[next_node]
q.append((cost + temp, next_node))
print(*ans[1:])
