[알고리즘] BOJ 14267 회사 문화 1 #Python

[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번의 직원까지 칭찬을 받은 정도를 출력하시오.

---

📍 풀이

💡 고찰

• 처음에는 트리를 생성해서 칭찬을 받을 때마다 재귀 함수를 이용하여 해당 직원에게 속해 있는 부하 직원의 칭찬 점수를 올리는 코딩 구조를 구현하였다.
• 구현 결과는 시간 초과와 메모리 초과였다.
  
• 시간 초과가 발생한 원인은 칭찬을 받을 때마다 재귀함수를 사용한 점이었다.
• 시간 초과 문제를 해결하기 위해선 직속 상사와 부하 직원의 양뱡향 연결 관계와 누적합 방식을 적용해야 했다.
• 플로이드 워셜 알고리즘 처럼 N번 처리해야할 일을 한번에 처리할 수 있는 방법이 있는지 항상 염두에 두어야 겠다.

📌 문제 풀이

✏️ [0] 재귀 함수

def recursive(i):
    points[i] += points[parents[i]]
    for child in children[i]:
        recursive(child)

• 현재 직원(i)의 칭찬 점수(points)에 직속 상사(parents[i])의 점수를 더한 후 현재 직원(i)의 후배 직원들을 대상으로 재귀를 진행한다.
• 해당 방식은 누적합 방식을 사용한다.

✏️ [1] 칭찬 점수 초기화

points = [0] * (n+1)
for i, w in compliments:
    points[i] += w

• 칭찬 점수 리스트(points)를 생성한 후 칭찬 점수를 초기화 한다.

✏️ [2] 양방향 트리 생성 및 초기화

parents = {i : 0 for i in range(1,n+1)}
children = {i : [] for i in range(1,n+1)}
for i in range(1, n):
    parents[i+1] = relations[i]
    children[relations[i]].append(i+1)

• 부모 정보에 해당하는 트리(parents)와, 자식 정보에 해당하는 트리(children)를 각각 생성하여 값을 초기화 한다.

✏️ [3] 재귀 함수 실행

recursive(1)

• 가장 최상위 직원인 1 의 값을 인자로 재귀 함수를 실행한다.

✍ 코드

from sys import stdin, setrecursionlimit
setrecursionlimit(1000000)

def solution(n,relations,compliments):
    # [0] 재귀 함수
    def recursive(i):
        points[i] += points[parents[i]]
        for child in children[i]:
            recursive(child)
    
    # [1] 칭찬 점수 초기화
    points = [0] * (n+1)
    for i, w in compliments:
        points[i] += w

    # [2] 양방향 트리 생성 및 초기화
    parents = {i : 0 for i in range(1,n+1)}
    children = {i : [] for i in range(1,n+1)}
    for i in range(1, n):
        parents[i+1] = relations[i]
        children[relations[i]].append(i+1)
        
    # [3] 재귀 함수 실행
    recursive(1)

    return points

# input
n, m = map(int,stdin.readline().split())
relations = list(map(int,stdin.readline().split()))
compliments = list(list(map(int,stdin.readline().split())) for _ in range(m))

# result
result = solution(n,relations,compliments)
print(*result[1:])