[Python] 프로그래머스: 여행경로

프로그래머스

 

🐰 문제

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

🐰 제한 사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

🐰 입출력 예

 

🥕 문제 풀이

  모든 경로를 탐색한다는 점에서 DFS를 이용하여 풀이했다.

def solution(tickets):
    
    answer = ["ICN"] # 가능한 경로들을 저장할 리스트 (가능한 경로가 2개 이상일 수 있다)
    visited = [False] * len(tickets)
    
    def dfs(airport, path): 
        # 모든 경로를 탐색한 경우 return
        if len(path) == len(tickets) + 1:
            answer.append(path)
            return
        
        # 연결 노드 순회
        for idx, ticket in enumerate(tickets):
            # 티켓의 0번 인덱스가 이전 경로를 뜻하는 airport와 같고, 방문하지 않은 경로일 경우
            if ticket[0] == airport and not visited[idx]:
                visited[idx] = True
                dfs(ticket[1], path + [ticket[1]]) # +: 두 리스트 합치기, append(): 추가 [[]]
                visited[idx] = False # 만약 가능한 경로가 두 개일 경우 고려
                
    dfs("ICN", ["ICN"])
    
    answer.sort()
    
    return answer[0]

  dfs 메서드의 매개변수 airport는 현재 노드를, path는 경로를 의미한다.

경로의 수 = (항공권의 수 + 1)일 때 하나의 경로를 모두 탐색했음을 의미한다. 이를 재귀 함수의 종료 조건으로 두고, dfs 메서드 밖에 선언해 둔 리스트 answer에 추가한다. path를 바로 반환하지 않고 answer에 추가하는 이유는 문제에 '가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 한다.'는 조건이 있으므로 가능한 경로들을 우선 answer에 넣어 두는 것이다.

tickets 내부의 각 리스트들에 enumerate로 인덱스를 붙인다. 리스트의 0번 인덱스가 의미하는 공항에서 1번 인덱스의 공항으로 이동할 수 있다는 의미이므로 0번 인덱스가 현재 노드와 같고, 아직 방문하지 않은, 즉, 사용하지 않은 항공권이라면 방문 처리를 한 뒤에 dfs 재귀 함수를 실행하도록 한다.

이때 매개변수로 탐색할 다음 노드인 1번 인덱스의 값과 현재까지의 경로 path와 다음 경로를 합친 리스트를 넣어 준다. 재귀 함수를 실행한 이후 만약 가능한 경로가 두 개일 경우를 고려해서 해당 노드의 방문 여부를 False로 바꿔 줘야 한다.

[예시]

[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]

1. ICN -> SFO로 시작하는 경로가 먼저 탐색된다.
2. ICN -> ATL로 시작하는 경로가 탐색될 때 1번 경로의 방문 처리가 되어 있지 않아야 다음 탐색 경로에 포함된다.

dfs 메서드가 종료되면 answer에 저장된 리스트들을 정렬하고(알파벳 순서로 정렬), 0번 인덱스를 반환하도록 한다.