백준 14267 - 회사 문화 1 ( Python )

https://www.acmicpc.net/problem/20955

문제설명

상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다.

칭찬에는 수치가 존재해서, 이 수치 또한 부하들에게 똑같이 칭찬을 받는다.

해결방법

처음으로 생각한 방법은 dfs로 직속상관부터 부하까지 방문하면서 칭찬수치를 더하여 문제를 풀이하였다.

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

n, m = map(int, input().split())

parent = list(map(int, input().split()))
graph = [[] for i in range(n+1)]

for i in range(1, len(parent)):
    graph[parent[i]].append(i+1)
    
answer = [0] * (n+1)

def dfs(x, cnt):
    answer[x] += cnt
    
    for i in graph[x]:
        dfs(i, cnt)    
    
for i in range(m):
    u, cnt = map(int, input().split())
    dfs(u, cnt)

for i in range(1, len(answer)):
    print(answer[i], end = ' ')

그러나 dfs로 부하직원을 탐색하는 행위가 시간초과로 이어지는 결과가 나왔다.

직원을 탐색하지않고 부하직원까지 점수를 더하는 방법을 찾아본 결과

부모의 점수를 그대로 더 해주기만 하면 된다는 사실을 알게 되었고 코드를 수정했다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

parent = [0] + list(map(int, input().split()))
point = [0] * (n + 1)

for i in range(m):          # 입력받은 칭찬점수를 더해주는 부분
    u, cnt = map(int, input().split())
    point[u] += cnt 

for i in range(2, n+1):     # 직속상관의 칭찬점수를 더해주는 부분
    point[i] += point[parent[i]]
    
for i in range(1, len(point)):            
    print(point[i], end = ' ')