BOJ 14267) 회사 문화1

문제

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,

입력

첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)

사장은 상사가 없으므로 칭찬을 받지 않는다.

출력

1번부터 n번의 직원까지 칭찬을 받은 정도를 출력하시오.

---

풀이

무식하게 접근해보면 직속 상사, 직속 부하 관계들을 모두 참고하여 i와 w가 들어올 때마다 모든 부하들의 연결을 순차 탐색해나간다.

정말 최악을 가정할 경우 O(n^n) 정도 될 것 같다.

이 점을 개선하기 위해서 트리를 이용한다. 직속 상사, 직속 부하 관계를 트리로 표현하면 탐색할 대상이 줄어들게 되어 효율적으로 접근할 수 있다.

문제에서 직속 부하의 부하들도 모두 동일한 칭찬을 받게 되므로 순회를 이용할 수 있을 것 같다.

우선 칭찬 받은 부하 i를 루트로 하는 서브 트리를 순회하여 연결된 모든 노드에 칭찬을 더한다.

이 연산을 m번 반복할 경우 최악의 경우 10^10의 연산이 필요하게 되어 시간 초과가 발생한다.

이 알고리즘의 수행 과정을 살펴보면 칭찬 점수가 누적된다는 사실을 알 수 있다. 그러니까, m번의 모든 입력이 주어졌을 때, 어떤 노드의 칭찬은 이 노드가 받은 칭찬 + 이 노드의 조상이 받은 칭찬들의 합이다.

이 점을 이용하면 한 번만 트리를 순회해도 문제 해결이 가능하다.

단, 입력이 트리라는 조건이 없다는 것에 주의해야 한다.

한 사람에게 여러 직속 상사가 있을 수도 있다. 그리고, 한 부하가 여러번 칭찬 받을 수도 있다. 이 점을 간과하여 여러번 틀렸다.

따라서 이 문제의 입력은 사이클이 있을 수 있는 그래프이다.

우선 그래프의 링크 연결을 구성한다. Adjacent list를 이용했고, 부하가 상사에게 칭찬할 일이 없으니 단방향으로 구성한다.

m번의 연산 동안 노드 i가 받은 칭찬들을 누적하여 저장한다. 초기 값은 0이다. 누적 되는 값들은 크기가 n+1인 리스트에 저장된다.

순회를 한 번 하면서 부모로부터 받은 칭찬과 자신이 받은 칭찬의 합을 결과 리스트에 저장한다.

i 번째 노드에 대한 칭찬 계산 연산은 부모 노드에 의해서 수행된다.
사이클에 대비하여 방문했음을 기록한다.

나는 BFS를 이용하여 재귀로 인한 오버헤드를 줄이고자 했다.

다음은 프로그램 전문이다.

import sys
from collections import deque
sys.setrecursionlimit(100000)

def bfs(tree, praise_cnt, root) :
    queue = deque()
    queue.append(root)
    visited = set()
    # 두 명 이상의 직속상사가 있을 경우를 고려함.
    while queue :
        cur_node = queue.popleft()
        if cur_node in visited :
            continue
        visited.add(cur_node)
        for v in tree[cur_node] :
            praise_cnt[v] += praise_cnt[cur_node]
            queue.append(v)

def solve() :
    n, m = map(int, sys.stdin.readline().split())
    tree = [[] for _ in range(n+1)]
    parents = tuple(map(int, sys.stdin.readline().split()))
    
    for i in range(1, len(parents)) :
        tree[parents[i]].append(i+1)
    
    praise_cnt = [0 for _ in range(n+1)]
    
    for _ in range(m) :
        senior_number, cnt = map(int, sys.stdin.readline().split())
        # 칭찬을 여러번 받을 경우를 고려해야한다.
        praise_cnt[senior_number] += cnt
    
    bfs(tree, praise_cnt, 1)
    for i in range(1, n+1) :
        print(praise_cnt[i], end=(' ' if i < n else ''))
    
    return

solve()