[백준][Python] 14267번 회사 문화 1

14267번: 회사 문화 1

 

 

코드

처음에는 칭찬을 받은 직원을 입력받을 때마다 트리를 순회해서 해당 직원의 부하 직원을 모두 찾아 값을 더해줬는데 시간 초과가 났다.

import sys
from collections import defaultdict
def dfs(a,b):
	visit = [False]*(n+1)
	queue = []
	queue.append(a)
	while queue:
		next = queue.pop()
		if visit[next]:
			continue
		visit[next] = True
		total[next] += b
		for i in tree[next]:
			if not visit[i]:
				queue.append(i)


n,m = map(int,input().split())
n_list = list(map(int,input().split()))
total = [0]*(n+1)
tree = defaultdict(list)
for i in range(1,n):
	tree[n_list[i]].append(i+1)

for i in range(m):
	a,b = map(int,sys.stdin.readline().split())
	dfs(a,b)
print(*total[1:])

 

시간 초과 문제를 해결하기 위해 일단 칭찬을 받은 당사자에게만 칭찬 수치를 더해줬다. 그리고 나서 한번에 트리를 순회하면서 자신의 직속 상사의 칭찬 수치를 추가로 더해줬다.

import sys
from collections import defaultdict
def dfs(a):
	visit = [False]*(n+1)
	queue = []
	queue.append(a)
	while queue:
		next = queue.pop()
		if visit[next]:
			continue
		visit[next] = True
		
		for i in tree[next]:
			if not visit[i]:
				queue.append(i)
				total[i] += total[next]  # 직속 상사의 칭찬 수치 더해줌


n,m = map(int,input().split())
n_list = list(map(int,input().split()))
total = [0]*(n+1)
tree = defaultdict(list)
for i in range(1,n):
	tree[n_list[i]].append(i+1)

for i in range(m):
	a,b = map(int,sys.stdin.readline().split())
	total[a]+=b
dfs(1)
print(*total[1:])