[백준] 14267 회사 문화 1

문제 링크

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

사용 알고리즘

• DP
• DFS
• 트리
• 트리에서의 다이나믹 프로그래밍

풀이

이 문제를 풀기 전에 15681 트리와 쿼리를 먼저 풀어보는 것을 추천한다.
이 문제와 유사하면서 트리에서의 다이나믹 프로그래밍에 대해 이해하기 좋은 문제다.

 

 

우선, 가장 먼저 할 일은 직속 상사와 부하의 관계를 표현할 tree 구조를 만드는 것이다.

관계, 트리에서의 각 노드의 부모, 트리에서의 각 노드의 자손들을 저장할 배열을 만들어준 뒤 입력값을 통해 관계를 설정해주자.

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

connect, node_parent, node_children = [[] for _ in range(n)], [-1] * n, [[] for _ in range(n)]
for curr, parent in enumerate(map(lambda x: int(x) - 1, input().split()[1:]), start=1):
    # 노드 간 관계 저장
    connect[parent].append(curr)
    connect[curr].append(parent)


# 트리 구조를 만드는 함수
def make_tree(current_node: int, parent: int) -> None:
    """
    현재 노드의 자식을 순회하며 자신과 연결되어 있는 노드 중
    자신의 부모 노드가 아닌 노드의 부모를 자신으로 설정 & 현재 노드의 자식에 해당 노드를 추가
    자식 노드에 대해서도 이를 재귀적으로 반복
    """
    for node in connect[current_node]:
        if node == parent: continue

        node_children[current_node].append(node)
        node_parent[node] = current_node
        make_tree(node, current_node)


# 0번 직원(사장)은 상사가 존재하지 않기 때문에 parent=-1로 호출
make_tree(0, -1)

 

 

그 후, 각 직원이 받은 칭찬을 특정 배열에 저장해주자.

여기서 주의해야 할 점은 한 직원이 여러 번 칭찬받을 수도 있다는 점이다.

v = [0] * n
for _ in range(m):
    i, w = map(int, input().split())
    v[i - 1] += w

 

이제 0번 직원(사장)부터 시작해서 내가 받은 칭찬을 내 자손 직원에게 전파하는 함수를 작성해주자.

# 칭찬의 정도를 저장하는 dp 배열
dp = [0] * n


# 현재 직원이 받은 칭찬을 자식 직원에게 전파하는 함수
def calc(current_node):
    # 현재 직원이 받은 칭찬을 현재 직원의 칭찬 정도에 추가
    dp[current_node] += v[current_node]
    
    # 현재 직원의 모든 자식 직원에 대해 내 칭찬 정도를 전파 후 자식 직원에 대해서도 반복
    for node in node_children[current_node]:
        dp[node] += dp[current_node]
        calc(node)


# 0번 직원(사장) 부터 계산 시작
calc(0)

실행 과정

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

sys.setrecursionlimit(10 ** 6)

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

connect = [[] for _ in range(n)]
for curr, parent in enumerate(map(lambda x: int(x) - 1, input().split()[1:]), start=1):
    connect[parent].append(curr)
    connect[curr].append(parent)

v = [0] * n
for _ in range(m):
    i, w = map(int, input().split())
    v[i - 1] += w

node_parent, node_children, dp = [-1] * n, [[] for _ in range(n)], [0] * n


def make_tree(current_node, parent):
    for node in connect[current_node]:
        if node == parent: continue

        node_children[current_node].append(node)
        node_parent[node] = current_node
        make_tree(node, current_node)


def calc(current_node):
    dp[current_node] += v[current_node]
    for node in node_children[current_node]:
        dp[node] += dp[current_node]
        calc(node)


make_tree(0, -1)
calc(0)

print(*dp)