[Programmers][Level 3] 여행경로

DFS : Depth-First Search > 스택을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감

BFS : Breadth-First Search > 큐를 사용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행함

 

DFS를 응용

- 한붓 그리기 문제이다.

- 시작 정점은 "ICN"

- 모든 간선을 거쳐야됨

- 한 정점에서 택할 수 있는 간선이 여러 개인 경우 알파벳 순서를 따름 

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0],[]) + [t[1]]
    for r in routes:
        routes[r].sort(reverse = True)
    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][-1])
            routes[top].pop()
    
    return path[::-1]