node: 공항

edge: 항공권

모든 edge를 연결하는 directed path

알파벳순으로 DFS 해서 visited = [모든 node] or 거리 = len(tickets)이면 return

모든 항공권을 사용해야 한다.

현재 공항에서 사용하지 않은 항공권을 알파벳 순서대로 방문해본다.

현재 공항에서 사용할 수 있는 항공권이 없다면 멈춘다.(not promise)

같은 항공권 2개 있는 경우도 고려해야함.

def solution(tickets):
    graph = defaultdict(list)
    for s,e in tickets:
        graph[s].append(e)
    for adjs in graph.values():
        adjs.sort(reverse=True)

    stack = ["ICN"]
    path = []
    
    while stack:
        node = stack[-1]
        print(node, graph[node])
        if graph[node]:  # 다른 공항으로 출발 가능
            stack.append(graph[node].pop())
        else:  # 인접노드로 이동 불가능
            path.append(stack.pop())
    
    return path[::-1]

스택에는 순회 경로가 기록된다.

'''
directed graph
node: 공항
edge: 항공권 존재
'''

from collections import defaultdict, OrderedDict

def dfs(graph, start, ticket_num):
    if ticket_num == 0:
        return [start]
    elif start not in graph:  # start에서 출발하는 항공권 부재
        return None
    
    for end in graph[start]:
        if graph[start][end] > 0:
            graph[start][end] -= 1
            path = dfs(graph, end, ticket_num-1)
            if path:
                return [start] + path
            graph[start][end] += 1
    return None
        

def solution(tickets):
    graph = defaultdict(dict)
    ticket_num = 0
    for s,d in tickets:
        if not graph[s].get(d):
            graph[s][d] = 0
        graph[s][d] += 1
        ticket_num += 1
    
    print(graph)
    graph = {k: OrderedDict(sorted(graph[k].items())) for k in graph}
    return dfs(graph, 'ICN', ticket_num)
        
print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]))
print(solution([["ICN","A"],["A","B"],["B","A"],["A","ICN"],["ICN","A"]]))
print(solution([["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]]))

"""
graph[start]가 list
"""

from collections import defaultdict, OrderedDict

def dfs(graph, start, ticket_num):
    if ticket_num == 0:
        return [start]
    
    for i,end in enumerate(graph[start]):
        graph[start].pop(i)
        path = dfs(graph, end, ticket_num-1)
        if path:
            return [start] + path
        graph[start].insert(i, end)
    return None
        

def solution(tickets):
    graph = defaultdict(list)
    ticket_num = 0
    for s,d in tickets:
        graph[s].append(d)
        ticket_num += 1
    for l in graph.values():
        l.sort()
    
    return dfs(graph, 'ICN', ticket_num)

print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]))
print(solution([["ICN","A"],["A","B"],["B","A"],["A","ICN"],["ICN","A"]]))
print(solution([["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]]))