회사 문화 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번의 직원까지 칭찬을 받은 정도를 출력하시오.
트리를 생각해서 풀긴했는데 이진 트리는 아니고 인접리스트를 사용하여 풀었다.
그런데 40퍼 쯤에서 시간초과
import sys
# 직원 수, 칭찬 횟수
n, m = map(int,sys.stdin.readline().split())
emp_com = [0] * (n+1)
employer_ee = [[] for _ in range(n+1)]
# 상사 번호
sslist = list(map(int,sys.stdin.readline().split()))
for i in range(len(sslist)):
if sslist[i] == -1:
continue
employer_ee[sslist[i]].append(i+1)
def dfs(v,cnt):
stack = [v]
while stack:
node = stack.pop()
emp_com[node] += cnt
stack.extend(employer_ee[node])
# 칭찬 받은 직원, 횟수
for _ in range(m):
com = list(map(int,sys.stdin.readline().split()))
dfs(com[0],com[1])
print(" ".join(map(str,emp_com[1:])))
찾아보다가 dfs를 여러번해서 시간이 오래 걸린다는걸 알았다.
그래서 dfs를 한번만 할 수 없을까 생각해서 한 것이 미리 칭찬 횟수를 각 번호에 저장하고 dfs를 하면서 상사의 칭찬 횟수를 이어 받는 형식으로 하니깐 통과
import sys
# 직원 수, 칭찬 횟수
n, m = map(int,sys.stdin.readline().split())
# 칭찬 횟수 저장 리스트
emp_com = [0] * (n+1)
# 직속 부하 저장 리스트
employer_ee = [[] for _ in range(n+1)]
# 상사 번호
sslist = list(map(int,sys.stdin.readline().split()))
# 직속 부하 저장
for i in range(len(sslist)):
if sslist[i] == -1:
continue
employer_ee[sslist[i]].append(i+1)
# dfs 과정
def dfs(v):
stack = [v]
while stack:
node = stack.pop()
for chi in employer_ee[node]:
emp_com[chi] += emp_com[node]
stack.append(chi)
# 칭찬 받은 직원, 횟수
for _ in range(m):
com = list(map(int,sys.stdin.readline().split()))
# 각 칭찬 받는 직원에 횟수를 저장
emp_com[com[0]] += com[1]
# dfs 시작
dfs(1)
# 출력
for i in emp_com[1:]:
print(i,end=" ")
#print(" ".join(map(str,emp_com[1:])))
'@@@ 알고리즘 > 백준 스터디' 카테고리의 다른 글
14618(총깡 총깡) - 해결 (0) | 2021.09.05 |
---|---|
9765(여섯 방정식) - 시간 초과 - 참고 - 해결 (0) | 2021.09.01 |
2174(로봇 시뮬레이션) - 해결 (0) | 2021.08.27 |
21738(얼음깨기 펭귄) - 시간초과 - 해결(참고) (0) | 2021.08.26 |
2922(즐거운 단어) - 해결 (0) | 2021.08.26 |