[Programmers/Level 3/Python] 여행경로

Programmers(프로그래머스) 여행경로

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

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

예)
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]
=>["ICN", "JFK", "HND", "IAD"]

풀이

전형적인 DFS(깊이우선탐색) 활용 문제로, 고려해야 할 사항들은 다음과 같다.

1. 시작은 항상 "ICN"이다.  => DFS의 시작은 항상 "ICN"
2. 가능한 여행 경로가 둘 이상이라면, 알파벳 순서가 앞서는 경로를 return한다.
    => tickets을 오름차순으로 정렬한 뒤 DFS를 수행했을 때 가장 처음으로 찾는 완전한 여행 경로가 answer
3. 주어진 항공권을 모두 이용해야 한다.
4. 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.  =>여행 경로(answer)는 항상 존재
5. 중복된 항공권이 존재할 수 있다.  => 방문 여부를 Index 저장으로, 또는 별도의 리스트 상에 표시하는 것이 좋다.

Python으로 구현한 코드는 다음과 같다.

def solution(tickets):
    answer = []
    
    # start 지점부터 tickets 내에서 used_ticket에 없는(사용하지 않은) 항공권들로 여행경로 찾기
    def DFS(tickets, start, used_ticket):   
        # start에서 다음으로 이동할 공항 찾기
        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)  # 도착 항공에서부터 다음 여행경로 찾기
                # 항공권을 모두 사용한 경우 DFS 종료
                if len(used_ticket) == len(tickets):  
                    return
                # 도착 항공에서부터 다음 여행경로를 찾았음에도 항공권을 모두 사용하지 않은 것은
                # 해당 항공권을 지금 사용하는 것이 맞지 않으므로 used_ticket에서 삭제
                else:  
                    used_ticket.pop()
                
    new_tickets = sorted(tickets, key=lambda x: (x[0], x[1]))  # 항공권 오름차순 정렬
    used_ticket = []  # 사용한 항공권 index 저장하는 list
    DFS(new_tickets, "ICN", used_ticket)   # ICN을 시작으로 DFS 수행
    
    # 거쳐간 공항을 answer에 저장
    answer = ["ICN"]
    for ticket_num in used_ticket:
        answer.append(new_tickets[ticket_num][1])
                
    return answer