[백준-파이썬] 14267: 회사 문화1

트리.. 몇 번 들어본 것 같기는 한데, 잘은 모르고 있었다. 이번에 싸피에서도 트리를 배웠는데, 마침 스터디 과제로도 이 문제가 있어서 반가웠다 ㅎㅎ

접근 🤔

맨 처음에는 한 명의 직속 상사가 여러 명의 직속 부하가 있는 걸 생각 못해서 틀렸다.
그 다음에는 칭찬을 받을 때마다 쭉

~ 내려 보내서 시간 초과가 나왔다. (칭찬 받을 때마다, 그 칭찬받은 당사자를 루트 삼아서 쭉

트리를 순회하면서 직속 부하, 그 직속 부하, 그 직속 부하...에게 compliment 리스트에 칭찬의 수치를 더해줬다.)
그래서 일단은 칭찬이 입력될 때, 칭찬 받은 그 당사자만 칭찬을 받게 했다. (compliment 리스트에 더해서)
그 후에 트리를 1부터 전위 순회했다. 그러면서 직속 상사가 칭찬 받은 걸 더해서 받게 했다.

코드 👩‍💻

import sys

sys.setrecursionlimit(10 ** 6)

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

# 상사-부하 관계를 트리 형태로 저장
immediate_subordinate = [[] for _ in range(n + 1)]  # 직속 부하의 번호를 저장(직속 부하가 여러 명일 수도 있으니 리스트 형태로 저장)
immediate_superior = [0] * (n + 1)  # 직속 상사 번호를 저장 (직속 상사는 한 명이니까 그냥 숫자로 저장)
for i in range(len(immediate_superior_list)):
    if immediate_superior_list[i] == -1:
        continue
    immediate_subordinate[immediate_superior_list[i]].append(i + 1)
    immediate_superior[i + 1] = immediate_superior_list[i]

# 칭찬의 정보 저장하는 리스트 (인덱스 번호가 직원 번호)
compliment = [0] * (n + 1)


def pre_order(n): # 트리 순회 (전위)
    compliment[n] += compliment[immediate_superior[n]]  # 직속 상사가 칭찬 받은 걸 그대로 더해서 받으면 된다! 
    if immediate_subordinate[n]:  # 직속 부하가 있으면
        for i in range(len(immediate_subordinate[n])): # 그 직속 부하들까지 내려감
            pre_order(immediate_subordinate[n][i])


for i in range(m):  # 입력되는 칭찬 수
    receiver, com_value = map(int, input().split())  # 칭찬 받은 직원 번호, 칭찬의 수치
    compliment[receiver] += com_value  # 일단 바로 칭찬 받은 직원이 칭찬을 받고

# 당사자가 일단 칭찬 다 받은 후에, 자식에게 전파
pre_order(1)

compliment.pop(0) # 인덱스 편하게 쓰려고 처음에 0번 인덱스는 의미 없는 거라서 팝
print(*compliment)

후기 😆

다른 분들 코드를 보니까 내 시간이 압도적으로 길다.. ㅠㅠ 왜 그런지도 봐야겠다..
=> 나는 DFS를 써서 그렇다..! BFS로 하면 더 짧아진다. 또 for 문 두 개 가지고 짧게 짜신 코드도 봤다..!

버전 2 ✨

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어지는데, 이건 번호 순서대로 들어온다. (음.. 맨 처음에는 1번 직원의 직속 상사 번호, 그 다음은 2번 직원의 직속 상사 번호 .. 이렇게)
나는 사장은 상사가 없으므로 직속 상사 번호로 -1이 들어오는데, 이게 파이썬에서는 맨 뒤 인덱스를 가리키는 걸로 되어서 이상해질까봐 걱정이 되었다. 그래서 위에 코드에서는 매번 직속 상사 번호가 -1인지 확인해서, 그렇다면 continue로 처리했다.
그런데 생각해보니 어차피 직원의 번호 순서대로 직속 상사의 번호가 들어온다. 그러니까 맨 처음에는 1번 직원의 직속 상사 번호가 들어오는데, 1번 직원은 사장이다. 그러니까 그냥 직속 상사 번호 받아와서, 상사-부하 관계를 저장할 때 시작을 하나 빼고 시작하면 되는 거였다..!

시간이 줄어들었다 ㅎㅎ

import sys

sys.setrecursionlimit(10 ** 6)

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

# 상사-부하 관계를 트리 형태로 저장
immediate_subordinate = [[] for _ in range(n + 1)]  # 직속 부하의 번호를 저장(직속 부하가 여러 명일 수도 있으니 리스트 형태로 저장)
immediate_superior = [0] * (n + 1)  # 직속 상사 번호를 저장 (직속 상사는 한 명이니까 그냥 숫자로 저장)
for i in range(1, len(immediate_superior_list)):
    immediate_subordinate[immediate_superior_list[i]].append(i + 1)
    immediate_superior[i + 1] = immediate_superior_list[i]

# 칭찬의 정보 저장하는 리스트 (인덱스 번호가 직원 번호)
compliment = [0] * (n + 1)


def pre_order(n): # 트리 순회 (전위)
    compliment[n] += compliment[immediate_superior[n]]  # 직속 상사가 칭찬 받은 걸 그대로 더해서 받으면 된다! 
    if immediate_subordinate[n]:  # 직속 부하가 있으면
        for i in range(len(immediate_subordinate[n])): # 그 직속 부하들까지 내려감
            pre_order(immediate_subordinate[n][i])


for i in range(m):  # 입력되는 칭찬 수
    receiver, com_value = map(int, input().split())  # 칭찬 받은 직원 번호, 칭찬의 수치
    compliment[receiver] += com_value  # 일단 바로 칭찬 받은 직원이 칭찬을 받고

# 당사자가 일단 칭찬 다 받은 후에, 자식에게 전파
pre_order(1)

compliment.pop(0) # 인덱스 편하게 쓰려고 처음에 0번 인덱스는 의미 없는 거라서 팝
print(*compliment)

(아 그리고 다시 생각해보니까 전위순회는 이진 트리에서만 쓰는 말 같아서, 아닌 것 같고 dfs라고 하면 될것 같다)

버전 3 😎

def pre_order(n): # 트리 순회 (전위)
    compliment[n] += compliment[immediate_superior[n]]  # 직속 상사가 칭찬 받은 걸 그대로 더해서 받으면 된다!
    for i in range(len(immediate_subordinate[n])): # 그 직속 부하들까지 내려감
        pre_order(immediate_subordinate[n][i])

pre_order() 부분을 이렇게 고쳤다!
if immediate_subordinate[n]: # 직속 부하가 있으면 부분을 없애준 것이다.
직속부하 있는지 확인하지 않고 바로 for문을 돌려도 되니까 !
만약에 없다면 len이 0일 것이고, 그러면 for문을 하나도 안 도니까..

헉..아니.. 그런데 이렇게 하니까 더 오래 걸리잖아 ??ㅠㅠ

빅오... 그런 거.. 대충은 알겠는데, 잘은 모르겠다ㅠ
나도 딱딱 멋있게 계산해서
아하! 이래서 시간이 오래 걸렸군

~ 이렇게 고쳐야지

뚝딱뚝딱~~
이러고 싶다...
공부를 하자 📚📚