여행경로

• 모든 엣지를 포함하는 경로, 즉 오일러 패스를 찾으라는 문제이다. 그냥 흔히 알려진 DFS기반의 알고리즘을 사용하면 된다.
• 그래프를 인접 리스트로 표현하고, 각 리스트의 마지막에 있는 에지부터 방문하면서 엣지를 리스트에서 pop()하는 식으로 구현하였다. 즉, 리스트의 끝에 있는 엣지부터 사용하게 되므로, 알파벳 순으로 탐색하기 위해 리스트를 알파벳의 역순으로 정렬하였다
• 시간복잡도는 소팅에 O(ElogE) + 탐색에 O(E)인데, 문제에서 V≤10000 이라고만 주어지고, E에 대해서는 범위가 주어지지 않는다. 심플 그래프라는 보장이 없어서 E<V^2 인것도 보장이 안된다. 만약에 중복 엣지가 매우 많아서 E»V^2 라면, 그래프에 모든 엣지를 리스트에 넣는 것이 아니라, 중복 엣지를 묶어서 (엣지, 개수) 식으로 저장한다면 소팅 단계를 O(V^2logV)로 줄일수는 있을 것이다 (구현은 안함).

"""Solution code for "Programmers 43164. 여행경로".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43164
- Solution link: http://www.teferi.net/ps/problems/programmers/43164
"""

import collections


def dfs_rec(graph, u):
    ret = []
    while graph[u]:
        ret = dfs_rec(graph, graph[u].pop()) + ret
    return [u] + ret


def solution(tickets):
    graph = collections.defaultdict(list)
    for u, v in tickets:
        graph[u].append(v)
    for nodes in graph.values():
        nodes.sort(reverse=True)
    return dfs_rec(graph, 'ICN')