[리트코드] Reconstruct Itinerary(python)

리트코드, Reconstruct Itinerary_경로 재구성

TL;DR

• 깊이 우선 탐색(DFS)

문제 요약

1. 출발지와 도착지가 [출발지, 도착지] 형태로 주어진 배열에 대해서 경로를 재구성해서 반환하여라.
2. 'JFK'에서 출발하기 때문에 모든 입력에는 'JFK'가 있는 것이 보장된다.
3. 존재하는 여러 경로 중 가장 최소의 알파벳 순서로 된 경로를 반환해야 한다.
4. 모든 티켓은 최소 하나의 유효한 경로가 존재하며, 하나의 티켓은 한 번만 사용해야 한다.

 

- 모든 티켓을 사용하여 만들 수 있는 경로 중 가장 최소이며, 알파벳 순서로 돌아다니는 경로를 반환하면 된다.

입출력 형태

입출력 예시

 

- 예시 1의 경우, 그림에서 주어지는 그림과 같이 순서대로 이동하는 것이 유효한 최소 알파벳 순서의 경로이다.

- 예시 2의 경우, 여러 개의 경로가 존재할 수 있다. 여기서 알파벳 순서로 정렬된 형태가 문제에서 원하는 경로이다.

풀이

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        
        for _from, _to in sorted(tickets, reverse=True):
            graph[_from].append(_to)
            
        route = []
        
        def dfs(departure: str):
            while graph[departure]:
                dfs(graph[departure].pop())
            route.append(departure)
            
        dfs('JFK')
        return route[::-1]

 

이 문제의 경우 입출력 예시의 그림에서 확인할 수 있듯이 단방향 그래프 문제로 생각할 수 있다. 그렇기 때문에 입력 받는 tickets를 그래프로 만들어주는 작업이 필요하다. 이를 위해 비어 있는 리스트로 초기화된 defaultdict grpah를 선언해준다.

문제에서 알파벳 순서로 정렬된 경로를 원했기 때문에 입력받은 tickets를 정렬해서 graph를 생성한다. 이 때, dfs 함수에서 다루겠지만 pop을 해서 뒤쪽부터 뽑아낼 것이기 때문에 reverse를 True로 설정하였다. 이렇게 하면 출발지를 key로 도착지를 value로 하는 단방향 그래프를 생성할 수 있다.

 

dfs 함수에서는 방문지를 입력받아 방문지로부터 갈 수 있는 경로를 조회한다. 방문한 방문지는 pop 해서 방문했음을 표현한다. 순회가 완료되고 나면 방문지를 경로를 나타낼 route에 붙여준다.

 

백트래킹에 의해 가장 마지막 방문지부터 route에 들어가므로 정답을 반환할 때는 역순으로 반환해야 한다. 그렇기 때문에 `route[::-1]`을 반환하여야 한다.