[프로그래머스] 여행경로 python (*)

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

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

출처 : 프로그래머스

---

from collections import defaultdict
def solution(tickets):
    answer = []
    dic = defaultdict(list) # 유사 딕셔너리 생성
    
    for a,b in tickets:
        dic[a].append(b)
    for k in dic.keys():
        dic[k].sort(reverse = True) # 위에 있는 걸 먼저 내보내야해서 reverse
    print(dic)
    
    #dfs
    stack = ['ICN']
    while stack:
        top = stack[-1]
        if not dic[top]: # dic에 없으면 pop
            answer.append(stack.pop())
        else:
            stack.append(dic[top].pop())
            
    return answer[::-1]

풀이

defaultdict(list) : list 타입의 유사 딕셔너리 생성됨.

출발지를 key로 하고 sort()에서 reverse = True을 한다.

이 이유는 stack에서 가장 top에 있는 것으로 비교를 해서 pop() 연산을 할 것인데 여기서 더 편하게 하기 위함이다.

 

dfs 진행은 첫 시작 stack에 'ICN' 을 넣어주고 시작한다.

stack은 가는 경로라고 생각하면 된다.

dic[top] 의 값이 모두 stack에 들어가서 없어졌을 때, 모든 경로를 다 돈 것이다.

이제 이 stack 경로에 있는 원소들을 pop() 해서 answer에 넣어준다.

 

이때, 원하는 답과 거꾸로 얻어지기 때문에 최종적으로 뒤집어줘야 한다. -> answer [::-1]