[프로그래머스] Lv3. 여행경로 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43164
• 스택을 활용한 DFS를 사용

 

def solution(tickets):
    answer = []

    graph = {i[0] : [] for i in tickets}
    for i in tickets:
        graph[i[0]].append(i[1])
    for i in graph:
        graph[i] = sorted(graph[i], reverse=True)

    stack = ["ICN"] # 출발 위치 
    
    while stack:
        top = stack[-1] # 스택의 가장 위 요소(출발지)
        if top not in graph or not graph[top] : # 출발지가 없거나, 도착할 곳이 없으면
            answer.append(stack.pop())  # 스택에서 빼서 정답에 넣어준다.
        else:   # 도착할 곳이 있으면
            stack.append(graph[top].pop())  # 스택에 도착지를 넣어준다.

    answer.reverse()
    return answer