1. 문제 설명

여행경로

2. 문제 분석

모든 노드 방문이 아니라 모든 간선을 사용하는 경로를 탐색해야 한다. 특정 노드에서 출발하는 중복 간선을 허용하는 방향 그래프를 DFS로 풀자.

1. 주어진 ticket의 tail → head 정보를 바탕으로 딕셔너리로 만든다. 즉 특정 노드에서 갈 수 있는 인접 노드를 파악한다.
2. 현재 노드와 인접한 모든 노드를 각각 경로로 스택에 추가해가며 DFS를 하자. 이때 탐색 종료 기준은 티켓을 모두 사용하였는가이다. 즉 다음 노드로 이동할 때 현재 가지고 있는 티켓에서 그 경로를 제거해야 한다.
3. 모든 가능한 경로 중 알파벳 순서대로 정렬한 경우를 return한다.

• ticket이 리스트이기 때문에 새로운 객체를 만들지 않을 경우 각 경로가 사용하고 남은 ticket 개수를 파악할 수 없다. 자바라면 new, 파이썬이라면 list 함수로 감싸주어 새로운 객체를 만들자. 하나씩 remove하면서 정보를 반영하기 때문에 중복 간선 역시 다룰 수 있다.

3. 나의 풀이

def solution(tickets):
    nodes = {}
    for tail, head in tickets:
        adjacent = nodes.get(tail, [])
        adjacent.append(head)
        nodes[tail] = adjacent

    for key in nodes.keys():
        nodes[key].sort()
    
    # ticket의 tail -> head 간선 딕셔너리. 인접 노드는 알파벳 순서대로 정렬

    stack  = [["ICN", ["ICN"], list(tickets)]]
    answer = []
    # [현재 노드, 경로, 이 경로에서 사용 가능한 티켓]

    while stack:
        cur_node, path, remaining = stack.pop(-1)

        if not remaining: answer.append(path)
        # 모든 티켓을 사용할 수 있는 경로

        if nodes.get(cur_node):
            for adjacent in nodes.get(cur_node):
                next_path = path + [adjacent]

                if [cur_node, adjacent] not in remaining: continue
                # 현재 남아 있는 티켓에 해당 경로(현재 노드->인접 노드)가 없는 경우
                
                new_remaining = list(remaining)
                new_remaining.remove([cur_node, adjacent])
                # 사용한 티켓을 제거
                stack.append([adjacent, next_path, new_remaining])

    answer.sort()
    # 가능한 모든 경로를 알파벳 순서대로 정렬
    return answer[0]