[python] 백준 14267 회사 문화 1

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

14267번: 회사 문화 1

 

문제 해결

• 노드 하나를 잡고 그것을 루트(root)로 하는 서브트리의 모든 노드에 일정한 점수를 더하는 문제
• 점수를 더해줄 때 DFS를 쓰면 편하다는 것은 너무 쉽게 알 수 있다.
• 하지만 노드 하나씩 잡고 서브트리의 모든 노드에 일정한 점수를 더하는 것은 시간복잡도면에서 비효율적이며 시간초과가 나게 되었다.
• 루트로 잡을 노드에 모두 점수를 주입시키고 1번이 사장이라는 것(트리의 루트)라는 것을 이용해서 1번부터 내려가면서 점수를 누적시키는 방법이 효율적이라는 것을 알 수 있다.

 

CODE

import sys
sys.setrecursionlimit(10**6)

def DFS(s):
    visited = [False]*(n+1)
    queue = []
    queue.append(s)
    while queue:
        now = queue.pop()
        if visited[now]:continue
        visited[now] = True
        for i in child[now]: # child 부분 칭찬
            if not visited[i]:
                queue.append(i)
                answer[i] += answer[now]
if __name__=='__main__':
    n, m = map(int, input().split())
    parents = [-1] + list(map(int, input().split()))
    child = [[] for _ in range(n+1)]
    for i in range(1,n+1):
        if parents[i]==-1:continue
        child[parents[i]].append(i)
    answer = [0]*(n+1)
    for _ in range(m):
        i, w = map(int, input().split())
        answer[i] += w
    DFS(1)
    for i in range(1,n+1):
        print(answer[i], end=' ')