문제 링크

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

문제 설명

• 모든 항공권을 이용한 여행 경로 중 알파벳 순서가 가장 앞서는 경로 리턴

풀이

• 백트래킹
• 인접 리스트 초기화
• 스택에 경로 저장
• 스택의 크기가 항공권 개수에 다다르면 append
• sort 하여 알파벳 순서가 빠른 경로 리턴

코드

def solution(tickets):
    adj_dict, route, answer = init(tickets)
    dfs(adj_dict, route, answer, len(tickets), 'ICN')
    answer.sort()
    return answer[0]


def init(tickets):
    adj_dict = dict()
    for a, b in tickets:
        if a not in adj_dict:
            adj_dict[a] = []
        if b not in adj_dict:
            adj_dict[b] = []
        adj_dict[a].append([b, False])
    route = ['ICN']
    answer = []
    return adj_dict, route, answer


def dfs(adj_dict, route, answer, total, curr):
    if len(route) == total + 1:
        answer.append(route[:])
        return
    for i in range(len(adj_dict[curr])):
        nextt, visited = adj_dict[curr][i]
        if not visited:
            adj_dict[curr][i][1] = True
            route.append(nextt)
            dfs(adj_dict, route, answer, total, nextt)
            adj_dict[curr][i][1] = False
            route.pop()