[Python] 여행 경로

코딩테스트 연습 - 여행경로

풀이

1. 시작은 항상 "ICN"

2. 가능한 경로가 2개 이상이면 알파벳 순서가 앞서는 경로를 return -> tickets을 오름차순으로 정렬하고 찾은 완전한 경로가 정답

3. 주어진 항공권 모두 사용

4. 모든 도시를 방문할 수 없는 경우는 주어지지 않는다. -> answer는 항상 존재

5. 중복된 항공권 존재 -> 방문 여부를 인덱스로 관리

 

def solution(tickets):
    answer = []
    tickets.sort()
    used_ticket = []
    DFS(tickets, "ICN", used_ticket)
    
    answer = ["ICN"]
    for ticket_num in used_ticket:
        answer.append(tickets[ticket_num][1])
    
    return answer

def DFS(tickets, start, used_ticket):
    for i in range(len(tickets)):
        # 출발 공항이 start와 같으면서 사용하지 않은 티켓
        if tickets[i][0] == start and i not in used_ticket:
            used_ticket.append(i)
            DFS(tickets, tickets[i][1], used_ticket)
            
            if len(used_ticket) == len(tickets):
                return
            else:
                used_ticket.pop()