https://programmers.co.kr/learn/courses/30/lessons/77486

---

1. 전체 코드

from collections import defaultdict


def solution(enroll, referral, seller, amount):
    answer = []
    result = defaultdict(int)
    d = defaultdict(list)
    for i in range(len(enroll)):
        d[enroll[i]].append(referral[i])
    def dfs(name, price):
    	# 백트래킹 
        if price == 0:
            return 
        new_price = int(price * 0.1)
        result[name] += price - int(price * 0.1)
        for referral_name in d[name]:
            dfs(referral_name, new_price)
        
    for i in range(len(seller)):
        dfs(seller[i], amount[i] * 100)
    for i in range(len(enroll)):
        answer.append(result[enroll[i]])
    return answer

---

2. 후기

• 코드 설명

 for i in range(len(enroll)):
     d[enroll[i]].append(referral[i])
     
# d 출력
john ['-']
mary ['-']
edward ['mary']
sam ['edward']
emily ['mary']
jaimie ['mary']
tod ['jaimie']
young ['edward']

young의 추천인은 edward이다. 이 관계를 d에 저장한다.

그림을 보면 바로 이해가 될 것이다.

    def dfs(name, path: list, price):
        if price == 0:
            return
        new_price = int(price * 0.1)
        result[name] += price - int(price * 0.1)
        print(name, price - int(price * 0.1))

        for referral_name in d[name]:
            dfs(referral_name, path + [name], new_price)

    dfs('young', [], 1200)
    
# 출력
첫 번째 dfs print() -> young 1080
두 번째 dfs print() -> edward 108
세 번째 dfs print() -> mary 11
path = ['young', 'edward', 'mary']

설명을 위해 path와 print()를 사용했다.

if price == 0를 추가하지 않으면 테스트 케이스 11~13에서 런타임에러가 발생한다.

무의미한 dfs함수가 계속 실행되어 함수 호출 횟수를 초과한 경우이다.

추천인에게 보낼 금액이 0일 경우 함수를 바로 종료해야 한다.

백트래킹 조건을 다양하게 생각해보자