[백준][BFS][트리] 14367. 회사문화1

14367. 회사문화1

14267번: 회사 문화 1

 

• 첫 풀이
  • 시간초과
  • dfs

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

employee = [[] for _ in range(n+1)]
superior = list(map(int, input().split()))
compliment = [0 for _ in range(n+1)]


def dfs(emp_num, value):
    for k in employee[emp_num]:
        compliment[k] += value
        dfs(k, value)


for i in range(1, n+1):
    # 부하직원들을 담음
    if superior[i-1] <= 1:
        continue
    employee[superior[i-1]].append(i)

for _ in range(m):
    emp_num, v = map(int, input().split())
    compliment[emp_num] += v
    dfs(emp_num, v)

print(*compliment[1:])

 

• 두번째 풀이
  • bfs

from collections import deque, defaultdict

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

superior = list(map(int, input().split()))
employee = defaultdict(list)
# 직속 부하를 담음
for i in range(1, n):
    employee[superior[i]].append(i+1)
compliment = [0 for _ in range(n+1)]


def bfs(emp_num):
    visited = [False for _ in range(n+1)]
    queue = deque()
    queue.append(emp_num)

    while queue:
        x = queue.popleft()
        if visited[x] == True:
            continue
        visited[x] = True

        for emp in employee[x]:
            if not visited[emp]:
                queue.append(emp)
                # 부하한테 내칭찬 더해줌
                compliment[emp] += compliment[x]


for _ in range(m):
    emp_num, v = map(int, input().split())
    compliment[emp_num] += v

bfs(1)

print(*compliment[1:])