문제 설명

문제는 이 곳 링크를 참조하길 바란다.

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

---

전체 코드

from collections import defaultdict

def solution(tickets):
    
    def init_graph():
        routes = defaultdict(list)
        for key, value in tickets:
            routes[key].append(value)
        return routes

    def dfs():
        stack = ["ICN"]
        path = []
        while len(stack) > 0:
            top = stack[-1]

            if top not in routes or len(routes[top]) == 0:
                path.append(stack.pop())
            else:
                stack.append(routes[top].pop(0))

        return path[::-1]


    routes = init_graph()
    for r in routes:
        routes[r].sort()

    answer = dfs()
    return answer

---

해결 방법

다른 사람의 코드를 참조했다.

• https://wwlee94.github.io/category/algorithm/bfs-dfs/travel-route/

1. { 시작점 : [도착점], ... } 형태의 인접 리스트 그래프를 생성합니다.
   2.‘도착점’의 리스트를 정렬합니다. (알파벳 순서로)
2. DFS 알고리즘을 사용해 모든 점을 순회합니다. (스택이 빌때까지)

• 스택에서 가장 위 데이터(top)를 가져옵니다.
• 가져온 데이터(top)가 그래프에 없거나, 티켓을 모두 사용한 경우, path에 저장
• 아니라면, 가져온 데이터(top)을 시작점으로 하는 도착점 데이터 중 가장 앞 데이터(알파벳순으로 선택해야하므로)를 가져와 stack에 저장

4. path를 역순으로 출력 !