파이썬 알고리즘 191번 | [백준 14267번] - 회사문화 DFS

Yunny.Log ·2022년 7월 1일

Algorithm

목록 보기

194/318

191. 회사문화

1) 어떤 전략(알고리즘)으로 해결?

dfs

2) 코딩 설명

각 사람의 칭찬을 모두 더해준 뒤 ㅡ dfs로 보내서 그들의 자손에게 자신의 칭찬을 물려주고 - 그들은 또 그들의 자손에게 칭찬을 물려주고 ,,, 하는 방식

<내 풀이>


import sys
sys.setrecursionlimit(10**6)
n,m = map(int, sys.stdin.readline().rstrip().split())

node = [[] for _ in range(n+1)] # 직원 n명의 직속상사 담는 리스트
sangsa = list(map(int, sys.stdin.readline().rstrip().split()))
compliment = [0 for _ in range(n+1)]

def dfs(num) : # 내 직속부하들에게도 점수를 상속해주기 
    for k in node[num] : # num의 직속부하들에 대해서 
            compliment[k]+=compliment[num] # 내가 가진 칭찬을 더해주고 
            dfs(k) # 걔네도 칭찬 나눠주도록 보내기 

for i in range(1,n+1) :
    if sangsa[i-1]!=-1 : 
        node[sangsa[i-1]].append(i) 
        # 각 상사마다 가지는 직속 부하들을 담아주기 

# 칭찬의 총 갯수 M마다 dfs를 돌면 시간초과가 
# 사람 i에 대한 칭찬을 미리 모두 더한 뒤
# dfs를 돌려야 한다 (출처 : https://leesh111112.tistory.com/124)

for j in range(m) : # 먼저 각 사람이 받은 칭찬 저장 후 
    happyPerson, w = map(int, sys.stdin.readline().rstrip().split())
    compliment[happyPerson]+= w 

dfs(1) # 사장님부터 칭찬 상속 검사 돌리면 된다. 

compliment = compliment[1::]
for i in compliment :
    print(i, end=" ")

<내 틀렸던 풀이, 문제점>

시간초과 (19%)

나는 칭찬 받을 때마다 dfs 돌렸는데 그럼 시간초과가 걸린다.

이 때, 칭찬의 총 갯수 M마다 dfs를 돌면 시간초과가 나므로 사람 i에 대한 칭찬을 미리 모두 더한 뒤
dfs를 돌려야 한다
출처 : https://leesh111112.tistory.com/124


import sys
sys.setrecursionlimit(10**6)

n,m = map(int, sys.stdin.readline().rstrip().split())

node = [[] for _ in range(n+1)] # 직원 n명의 직속상사 담는 리스트
sangsa = list(map(int, sys.stdin.readline().rstrip().split()))
compliment = [0 for _ in range(n+1)]

def dfs(num, sizeOfCompliment) :
    #print("dfffffs", num)
    for k in node[num] :
        if k>num :
            #print(k, ":", compliment[k], "///",num ,":", compliment[num])
            compliment[k]+=sizeOfCompliment
            dfs(k, sizeOfCompliment)

for i in range(1,n+1) :
    node[i].append(sangsa[i-1])
    if sangsa[i-1]!=-1 : node[sangsa[i-1]].append(i)

for j in range(m) : 
    i, w = map(int, sys.stdin.readline().rstrip().split())
    compliment[i]+= w 
    dfs(i, w)
    #print(compliment)
    #print()
for i in compliment[1::] :
    print(i, end=" ")