[BOJ / 백준] 14267 회사 문화 1 (G4^ / 트리) - Python

링크

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

 

 

 

 

문제 해석

상사가 직속 부하를 칭찬하면 부하가 부하의 직속 부하를 연쇄적으로 칭찬

칭찬한 정도만큼 부하들이 똑같이 칭찬 받음

 

 

입력
첫 번째 줄 : n m
  n : 직원 수
  m : 칭찬의 횟수

두 번째 줄 : n명의 직속 상사 번호

m개의 줄 : i w
  칭찬을 받은 직원 번호
  칭찬의 수치

 

 

출력

모든 직원이 칭찬 받은 정도를 출력

 

 

 

 

풀이 & 코드 해석

직장의 상하관계를 생각해보면 그래프에 사이클이 없다는 것을 쉽게 생각할 수 있습니다.

(A가 B의 상사이고, B가 C의 상사이고, C가 A의 상사인 경우는 있을 수 없다.)

 

따라서 이 문제는 트리 문제라고 생각해볼 수 있습니다.

 

 

문제를 보면 A가 칭찬을 받으면 직속 부하인 B도 칭찬을 받고, B의 직속 부하들도 똑같이 내리칭찬(갈굼)을 받는다고 되어 있습니다.

 

따라서 부모가 받은 칭찬의 정도가 자식에게 영향을 미치는데, 마치 내가 트리에서 몇 depth에 위치하는지를 찾는 것과 매우 흡사하게 풀 수 있을 것이라고 생각하였습니다.

 

 

따라서 트리에서 depth를 구하듯이 dfs를 통해 자식 노드들에게 내가 받은 칭찬만큼 값을 더해준다면 정답을 찾을 수 있었습니다. 

 

 

 

 

코드

import sys
sys.setrecursionlimit(10 ** 8)


def dfs(cur):
    for nxt in child[cur]:
        sz[nxt] = sz[nxt] + sz[cur]
        dfs(nxt)


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

child = [[] for _ in range(n + 1)]
pre = [0]
sz = [0] * (n + 1)

pre.extend(list(map(int, input().split())))

for i in range(2, n + 1):
    child[pre[i]].append(i)

for _ in range(m):
    i, w = list(map(int, input().split()))

    sz[i] += w


dfs(1)

for i in range(1, n + 1):
    print(sz[i], end=" ")

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java