[BOJ] 14267 회사문화1

14267 회사문화 문제 링크
문제 풀이 코드 링크

문제 요약

어느 회사원이 칭찬받으면, 해당 회사원의 직속 부하들도 같은 양만큼 칭찬을 받는다. 회사원들간의 상하관계가 주어지고, 이후 어떤 회사원이 얼마만큼의 칭찬을 받았는지 입력이 주어질 때, 1번부터 n번까지의 회사원이 칭찬 받은 정도를 출력한다.
직속 상사의 번호는 자신의 번호보다 작다.

구상

• 기본적인 트리 문제. 상하관계를 트리로 구성한다.
  • 이 때, 자신의 번호를 key, 직속 부하의 번호의 list를 value로 갖는 dictionary로 구성한다.

• 매번 칭찬을 입력받을 때마다 탐색을 하며 칭찬 수치를 더해주기 보다는, 칭찬을 각 사원별로 저장해두고, 마지막에 root부터 leaf까지 탐색을하며 칭찬 수치를 전달하는 편이 좋다(전자는 시간초과가 발생한다).

• 탐색하는 방법은 2가지가 있다.

  • 1번의 사장을 제외한 모든 회사원은 자신의 직속 상사를 갖기 때문에, 1번부터 DFS, BFS로 탐색하면 leaf까지 모두 탐색할 수 있다.
  • 상사의 번호는 무조건 자신의 번호보다 작기 때문에, 1번부터 N번까지 순서대로 탐색해도 된다. 이 경우 BFS와 탐색 순서가 유사.

• 탐색 중, 자신이 가진 칭찬 수치를 자신의 자식(부하)의 칭찬수치에 더한다.

도식

1. 트리 구성
   

2. 칭찬 수치 입력 받아 각 node에 저장
   

3. <1> node부터 탐색하며 본인의 수치를 자식 노드의 수치에 더한다.
   
   
   

구현

나는 dfs로 풀었다. 다만, 최악의 경우 모든 직원들이 각각 한명의 부하만을 가지며, 이 경우 재귀의 깊이가 100,000까지 들어간다. BOJ의 998의 재귀 깊이 제한은 대략 998이므로, 이 제한을 풀어주었다.

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100010) # recursion 제한 증가

# DFS로 현재 node의 칭찬 정보를 자식 node에게 전달하고 칭찬을 더한다.
def doCompliment(person, amount) :
  compliment[person] += amount # 부모로부터 받은 칭찬의 양을 지금 node에 더한다.

  if person in subordinate :
    for sub in subordinate[person] :
      doCompliment(sub, compliment[person])

N, M = map(int, input().split(' '))

superior = list(map(int, input().split(' ')))
subordinate = dict() # 부하를 저장하는 사전
compliment = [0 for i in range(N)]

# 상사 정보를 바탕으로 부하 정보를 구성
for i in range(N) :
  if superior[i]-1 not in subordinate :
    subordinate[superior[i]-1] = []
  subordinate[superior[i]-1].append(i)

# 칭찬 정보를 입력받아 각 사람에게 칭찬 수치를 더해준다.
for i in range(M) :
  person, amount = map(int, input().split(" "))
  compliment[person - 1] += amount

# 재귀적으로 시행하며 0번(사장) node부터 DFS 탐색
doCompliment(0, 0)

# 출력
for i in compliment :
  print(i, end=" ")