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

분류: dfs /

문제

문제 링크

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

 

풀이

def dfs(tickets, path, origin):
    path.append(origin)
    if not tickets:
        return True
    
    isDone = False
    for i, ticket in enumerate(tickets):
        if ticket[0] == origin:
            restTickets = tickets[:i] + tickets[i+1:]
            destination = ticket[1]
            isDone = dfs(restTickets, path, destination)
            if isDone:
                break
            else:
                path.pop()
    return isDone

/*
def dfs(tickets, path, origin):
    path.append(origin)
    if not tickets:
        return True
    
    for i, ticket in enumerate(tickets):
        if ticket[0] == origin:
            restTickets = tickets[:i] + tickets[i+1:]
            destination = ticket[1]
            if dfs(restTickets, path, destination):
                return True
            path.pop()
    return False
*/

def solution(tickets):
    tickets.sort()
    path = []
    dfs(tickets, path, 'ICN')
    return path

알파벳 순서로 순회하기 때문에 `tickets`를 정렬해줍니다.

`dfs`가 실행되면 출발지를 `path`에 추가합니다.

dfs를 돌며 트리의 최대 깊이 까지 내려가면(탐색 성공), 그대로 roll up해 모든 콜스택을 종료합니다. 종료되면 `path`에 `dfs`가 실행된 순서대로 `origin`이 담겨 답을 얻을 수 있습니다.

티켓을 다 사용하지 못하고 탐색이 끝나면(탐색 실패),  넣었던 `origin`을 pop으로 지우고 다음 자식 노드를 방문합니다. (`origin`에서 출발하는 티켓이 남아있지 않아 티켓이 남아있는데도 재귀 호출이 일어나지 않는 경우입니다.)

 

탐색 성공인지 아는 것은 쉽습니다. 남은 티켓의 수가 0이면 모든 티켓을 사용한 것이니 탐색 성공입니다.(최대 깊이까지 내려간 경우입니다.)

핵심은 탐색 성공이라는 상태를 최대 깊이 리프노드에서 루트까지 모든 조상 노드에 전달하는 것입니다. 

저는 `isDone` 변수를 만들어 탐색 성공/실패를 반환하는 것으로 탐색 성공 여부를 조상노드로 전파했습니다.

사실 `isDone`변수를 사용하지 않고 break 대신 return True, 함수 마지막에 return isDone 대신 return False를 해도 되지만 의미를 파악하기 쉽게 isDone을 사용했습니다.

모든 노드는 자식노드의 성공/실패 여부를 전달 받습니다. 만약 자식 노드가 성공했다면 모든 행위를 멈추고 성공을 반환하여 자식 노드의 성공을 부모로 전달합니다. 이런 전달이 연속으로 이루어져 최대 깊이부터 루트까지 성공이 전파되며 종료됩니다.

탐색 성공(티켓을 모두 사용한 경우)이면 마지막 `origin`(전체 `path`에서는 최종 도착지 입니다.)을 저장하고 탐색 성공(True)를 반환하고 종료합니다.