[백준] 14267 회사 문화 1 (파이썬)

골드 Ⅳ

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

14267번: 회사 문화 1

 

📄 문제

• 영선회사에는 매우 좋은 문화가 있는데,
• 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다.
• 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.
• 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬받는다.

 

직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오.

 

---

💡 아이디어

• 트리 구조의 그래프이다.
• 상사가 가지고 있는 칭찬 수치를 새로운 배열에 저장해놓는다.
• 사장부터 부하직원을 순서대로 탐색하며 가지고 있는 칭찬 수치를 더 해간다. (DP)

---

깊이 우선 탐색, 동적 계획법(DP) 두 가지 방법을 활용하여 알고리즘을 풀이했다.

 

🟩 첫 번째 아이디어 (DFS, 깊이 우선 탐색)

• 문제에 주어진 직속 상사의 번호를 부하 직원을 알려주는 그래프로 재구성한다.
• 각 상사의 노드에 부하직원의 번호를 저장한다. (새로운 tree 배열을 만든다.)
• 칭찬 수치를 저장할 compliment 배열을 만든다.
• compliment 배열에 칭찬받은 직원 번호를 인덱스로 활용하여 각 칭찬 수치를 저장한다.
• 사장을 시작으로 각 직원의 부하직원을 dfs로 탐색한다.
• dfs로 탐색하며 compliment에 저장되어 있는 각 상사의 칭찬 수치를 부하직원 칭찬 수치에 더해준다.

 

✅ 두 번째 아이디어 (DP, 동적 계획법, 다이나믹 프로그래밍) - 최종코드 

• 문제에 주어진 직속 상사 번호를 인덱스와 통일시켜 superior에 배열로 저장한다.
• 칭찬 수치를 저장할 compliment 배열을 만든다.
• compliment 배열에 칭찬받은 직원 번호를 인덱스로 활용하여 각 칭찬 수치를 저장한다.
• 사장부터 부하직원을 순서대로 탐색한다.
• 각 직원이 가지고 있는 칭찬 수치를 부하 직원의 칭찬 수치에 더 해간다.
• 1번부터 N번까지의 직원들이 가지고 있는 칭찬 수치를 출력한다.

 

📝 문제 풀이 (Code)

최종 코드 ( 실행시간 196ms, 메모리 42612KB )

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
# 직원 번호 인덱스 통일
superior = [0] + list(map(int, input().split()))
# 칭찬 수치 저장
compliment = [0]*(n+1)

# 칭찬받은 각 직원의 칭찬 수치 저장
for _ in range(m):
    i, w = map(int, input().split())
    compliment[i] += w

for i in range(2, n + 1):
    # 상사가 가지고 있는 칭찬 수치를 부하직원에게 추가해줌
    compliment[i] += compliment[superior[i]]

print(*compliment[1:])

---

처음 코드 ( 실행시간 348 ms, 메모리 71208 KB )

DFS, 깊이 우선 탐색을 이용한다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(v, w):
    global compliment

    for k in tree[v]:
        compliment[k] += w
        dfs(k, compliment[k])


n, m = map(int, input().split())
superior = list(map(int, input().split()))
# 부하직원 저장
tree = [[] for _ in range(n+1)]
# 칭찬 수치를 저장
compliment = [0]*(n+1)

# 부하직원을 기준으로 저장하는 배열
for p in range(n):
    # 인덱스+1이 부하직원
    # super은 상사
    super = superior[p]
    if super > 0:
        tree[super].append(p+1)

# 칭찬받은 각 직원의 칭찬 수치 저장
for _ in range(m):
    i, w = map(int, input().split())
    compliment[i] += w

# 한번에 칭찬 수치 처리하기
dfs(1, compliment[1])
print(*compliment[1:])

 

시간초과 (19%)

• DFS, 깊이 우선 탐색
• 각 직원이 칭찬받을 때마다 DFS, 깊이 우선 탐색을 하게 되어 시간 초과 발생

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(v, w):
    global compliment

    compliment[v] += w

    for k in tree[v]:
        dfs(k,w)


n, m = map(int, input().split())
superior = list(map(int, input().split()))
# 부하직원 저장
tree = [[] for _ in range(n+1)]
# 칭찬 수치를 저장
compliment = [0]*(n+1)

# 부하직원을 기준으로 저장하는 배열
for p in range(n):
    # 인덱스+1이 부하직원
    # super은 상사
    super = superior[p]
    if super > 0:
        tree[super].append(p+1)
        
# 각 직원이 칭찬 받을 때마다 부하 직원의 칭찬 수치 저장
for _ in range(m):
    i, w = map(int, input().split())
    dfs(i, w)

print(*compliment[1:])