백준 14267 회사 문화 1 파이썬 풀이

난이도 : 골드 4

풀이일 : 2404011

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

14267번: 회사 문화 1

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys
sys.setrecursionlimit(10 ** 9)


# 내 자식들에게 나의 칭찬 점수 누적합산
def DFS(x):
    for nx in tree[x]:
        result[nx] += result[x]
        DFS(nx)
    return


n, m = map(int, sys.stdin.readline().split())
parents = list(map(int, sys.stdin.readline().split()))
tree = [[] for _ in range(n + 1)]  # 자식 정보
result = [0] * (n + 1)  # 칭찬 점수

# 자식 정보 기록
for i in range(1, n):
    tree[parents[i]].append(i + 1)

# 나의 칭찬 점수 계산
for _ in range(m):
    i, w = map(int, sys.stdin.readline().split())
    result[i] += w

# 각 자식 탐색하며 칭찬 점수 누적
DFS(1)

# 0 인덱스 삭제 후 출력
result = result[1::]
print(*result)

• 재귀 깊이를 늘려주지 않을 경우, 런타임에러가 발생하여 재귀 깊이를 10의 9 제곱으로 설정해주었다.
• DFS : 나의 칭찬 점수를 나의 모든 부하들, 그 부하들의 부하들에게 누적하여 합산해준다.
• parents : 주어지는 직속 상사 관계를 저장하여 tree를 구성한다.
• tree : 부하 정보를 저장한다. n번째 인덱스는 직속 상사, 그 내부에 추가된 요소들은 직속 부하로 보면 된다.
• result : 각 사원들의 칭찬 점수를 기록한다.
• 칭찬 점수 계산 시, 모든 칭찬을 입력 받은 뒤, 한 번에 DFS로 누적해준다.
• 사장부터 시작하여, DFS 함수를 통해 각 칭찬 점수를 계산해준다.
• 1번 부터 직원에 해당하니, 0번 인덱스를 제외하고 result를 출력 형식에 맞추어 출력한다.

---

느낀점

• 처음에는 시간초과로 한 번 틀리고, 다음에는 런타임에러로 한 번 틀렸다. 알고리즘의 시간 복잡도를 계산하고, 코드가 돌아갈 때 발생할 문제가 없는지 미리 꼼꼼하게 생각하며 문제를 풀자.