#33 [파이썬] 프로그래머스: 여행경로

<문제>

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

코딩테스트 연습 - 여행경로

 

---

 

<소스코드>

from collections import defaultdict

def dfs(dic, route, n):
    if len(route) == n+1:
        return route
    for i, r in enumerate(dic[route[-1]]):
        dic[route[-1]].pop(i)
        answer = dfs(dic, route+[r], n)
        dic[route[-1]].insert(i, r)
        if answer:
            return answer

def solution(tickets):
    dic = defaultdict(list)
    for key, value in tickets:
        dic[key].append(value)
    for key in dic.keys():
        dic[key].sort()
        
    answer = dfs(dic, ['ICN'], len(tickets))
    return answer

 

---

 

<NOTE>

• 재귀함수를 종료하기 위한 방법으로 조건문을 통해 return하는 방식 외에, 재귀함수가 호출되는 코드가 실행되지 않도록 하는 방법도 있다. 위의 코드에서는 dic[route[-1]]이 빈 리스트일 경우, for문을 돌지 않아서 dfs함수가 실행되지 않는다. 이때는 반환값이 없는 상태로 재귀문이 종료가 된다.
• 핵심 예시 tickets=[['ICN', 'CBA'], ['ICN', 'ABC'], ['CBA', 'ICN'], ['ABC', 'ULS']]