프로그래머스 여행경로 코드 및 해설 (파이썬)

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

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

 

💡 재귀함수를 이용해 풀이했습니다.

 

재귀함수 __help 내에선 아직 사용하지 않은 티켓들의 리스트를 하나씩 확인하면서, 마지막으로 방문한 공항에서 출발하는 티켓들을 확인합니다. 이에 해당하는 모든 티켓들에 대해 다시 재귀함수를 호출하는데, 이때 tickets에서 현재 티켓은 제외하고, answer에는 현재 티켓의 도착 공항을 추가하여 호출합니다.

만약 모든 티켓을 사용했다면 올바른 여행경로이므로 해당 answer를 candidates에 추가해줍니다. 그렇지 않은 경우, 현재의 answer는 저장되지 않고 다른 순서의 여행 경로를 확인하게 됩니다.

 

이후 solution 함수에서 이 candidates를 받고, 이를 알파벳 순으로 정렬해 첫번째 값을 반환합니다.

 

def __help(tickets, answer, candidates):
    
    for i, ticket in enumerate(tickets):
        # 마지막 방문 공항(answer[-1])과 이번 티켓의 출발 공항(ticket[0])이 같으면
        if ticket[0] == answer[-1]:    
            # 현재 티켓을 제외한 tickets, 현재 티켓의 도착 공항을 더해준 answer, candidate
            __help(tickets[:i] + tickets[i+1:], answer + [ticket[1]], candidates)
    
    # 모든 티켓을 사용한 경우 
    if not tickets:
        candidates.append(answer)
        
    return candidates

def solution(tickets):
    answer = ['ICN']
    # 모든 티켓을 사용할 수 있는 경로 
    candidates = []
    
    candidates = __help(tickets, answer, candidates)
    
    # candidate 중에서 알파벳 순서가 가장 앞서는 경로 
    return sorted(candidates)[0]