[프로그래머스, 파이썬] 다단계 칫솔 - 레벨 3 | BFS

📌 프로그래머스 Level 3 : 다단계 칫솔

문제는 복잡해보이지만, 상위 노드만 잘 타고 올라가면 쉽게 해결할 수 있는 문제!

이번 주에 푼 문제 중에 가장 수월하게 푼 문제다...

📝 내 답안

from collections import deque
def solution(enroll, referral, seller, amount):
    answer = [0 for _ in range(len(enroll))]
    # 그래프 만들기
    graph = {}
    i = 0
    for e,r in zip(enroll, referral):
        graph[e] = [r, i]
        i += 1

    # (seller, 수익금) 해당 seller부터 상위 노드로 올라가며 수익 배분
    def bfs(s, profit):
        q = deque()
        q.append((s,profit))
        while q:
            cur_s, p = q.popleft()
            if cur_s == "-":
                break
            refe_s = graph[cur_s][0]
            next_p = p//10
            answer[graph[cur_s][1]] += p
            if next_p < 1:
                break
            answer[graph[cur_s][1]] -= next_p
            q.append((refe_s,next_p))
    
    # for문으로 (seller, 수익금) 돌리면서 answer 갱신
    for i in range(len(seller)):
        bfs(seller[i],amount[i]*100)
    
    return answer

🔮 풀이

다음 알고리즘에 따라 문제를 풀었다.

1. graph 생성하기 : graph[seller] = [추천인, 인덱스]

2. 탐색 및 answer 갱신 : 해당 seller의 추천인의 추천인의 추천인 ... "-"(=center, 가장 상위 노드)를 만날 때 까지 탐색하며 answer 갱신

    # (seller, 수익금) 해당 seller부터 상위 노드로 올라가며 수익 배분
    def bfs(s, profit):
        q = deque()
        q.append((s,profit))
        while q:
            cur_s, p = q.popleft()
            # 가장 상위 노드인 "-"를 만나면 break
            if cur_s == "-":
                break
            # 현재 seller의 추천인
            refe_s = graph[cur_s][0]
            # 추천인이 가져갈 수익 = 현재 seller가 창출한 수익의 10%
            next_p = p//10
            # 현재 seller에 수익금 할당(10% 제외 아직 안함)
            answer[graph[cur_s][1]] += p
            '''
            !!! 만약 수익금의 10%가 1보다 작으면 
            추천인에게 수익을 할당하지 않고,
            현재 seller가 모두 가짐 !!!
            '''
            if next_p < 1:
                break
            # 그렇지 않으면 수익금의 10% 삭감
            answer[graph[cur_s][1]] -= next_p
            # (추천인,10% 수익금) 큐에 삽입하여 탐색 진행
            q.append((refe_s,next_p))