백준 14267 [회사 문화 1] 파이썬

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

 

# 백준 14267 회사 문화 1
import sys
from collections import deque
input = sys.stdin.readline

# N: 직원 수, M: 칭찬 횟수
N, M = map(int, input().split())

# 각 직원의 부하 목록을 저장할 리스트
sub = [[] for _ in range(N + 1)]

# bosses[i]는 i+2번 직원의 상사 번호
# 예: bosses[0]는 2번 직원의 상사
bosses = list(map(int, input().split()))

# 각 직원의 칭찬 점수를 저장할 리스트
scores = [0 for _ in range(N + 1)]

# 부하 관계 구성: sub[상사]에 부하를 추가
for i in range(2, N + 1):
    sub[bosses[i - 1]].append(i)

# 칭찬 점수 전파 함수 (BFS 방식)
def chk_score(node, above_score):
    q = deque()
    q.append((node, above_score))

    while q:
        curr_node, above_score = q.popleft()
        # 현재 노드의 점수에 상사의 점수 누적
        scores[curr_node] += above_score
        # 부하에게 점수를 누적하여 전파
        for next_node in sub[curr_node]:
            q.append((next_node, scores[curr_node]))

# M개의 칭찬 정보 반영
for _ in range(M):
    n, s = map(int, input().split())
    scores[n] += s  # 초기 본인 점수에 칭찬점수 더함

# 1번 직원(사장)부터 전체 전파 시작
chk_score(1, scores[1])

# 결과 출력 (1번부터 N번까지)
print(*scores[1:])

1. 회사 상사-부하 직원들간의 관계를 정리

2. 모든 칭찬을 일단 저장

3. 사장부터 아래로 내려가면서 모든 칭찬에 대해 반영하여 덧셈