[파이썬] [DFS] Pro 여행경로

문제

https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3 

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

 

코드

from collections import defaultdict

def solution(tickets):
    answer = []
    routes=defaultdict(list)

    for ticket in tickets:
        routes[ticket[0]].append(ticket[1])

    for key in routes.keys():
        routes[key].sort(reverse=True)

    stack=["ICN"]

    while stack:
        temp=stack[-1]
        if not routes[temp]:
            answer.append(stack.pop())
        else:
            stack.append(routes[temp].pop())
    answer.reverse()

    return answer

생각 정리

routes = {
    "ICN": ["SFO", "ATL"],
    "SFO": ["ATL"],
    "ATL": ["SFO", "ICN"]
}

temp="ICN"일 때 

"ICN" dict에서 pop()

routes = {
    "ICN": ["SFO"], //"ATL" 빠짐
    "SFO": ["ATL"],
    "ATL": ["SFO", "ICN"]
}

routes = {
    "ICN": ["SFO"],
    "SFO": ["ATL"],
    "ATL": ["SFO"] //"ICN" 빠짐
}

routes = {
    "ICN": [], //"SFO" 빠짐 
    "SFO": ["ATL"],
    "ATL": ["SFO"]
}