[LeetCode] 332. Reconstruct Itinerary

문제 출처: https://leetcode.com/problems/reconstruct-itinerary/

Reconstruct Itinerary - LeetCode

---

문제

항공권 리스트 $tickets$가 주어진다. $tickets[i] = [from_i, to_i]$는 출발지와 도착지를 표현하고 있다. 여행 일정을 세우고, 반환하라.

 

모든 tickets는 "JFK"에서 출발하는 사람의 것이기 때문에, 여행 일정은 "JFK"에서 시작해야 한다. 만약 세울 수 있는 여행 일정이 다양하다면, 여행 일정을 하나의 문자열로 읽을 때, 사전 순으로 가장 작은 여행 일정을 반환해야 한다.

• 예를 들어, 여행 일정 ["JFK", "LGA"]는 ["JFK", "LGB]보다 더 작다.

 

주어지는 tickets에는 최소 한 개의 가능한 일정이 존재함을 가정해도 된다. 주어지는 모든 티켓을 사용해야 하며, 각 티켓은 한 번씩만 사용할 수 있다. 

예제

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

---

풀이

문제 이해를 위해 주어진 예제 그림에서 파악할 수 있듯이 그래프 탐색 알고리즘을 통해 해답을 얻을 수 있습니다. 기본적인 그래프 탐색 알고리즘 중 DFS(깊이 우선 탐색) 기법을 이용하여 접근할 수 있습니다.

 

BFS를 사용하지 않는 이유는 여행 경로가 이어져야 하기 때문입니다. 예로 들어 A에서 B로 이동하는 항공편을 이용했다고 한다면, 다음 여행 경로는 B에서 출발하는 항공편이어야지, 뜬금없이 A에서 출발하는 항공편을 이용할 수는 없습니다.

 

DFS를 통해 문제를 해결하기에 앞서, 주어진 tickets를 그래프의 형태로 변경하는 과정을 수행합니다. 여기서는 임의의 출발지에서 이동할 수 있는 리스트를 빠르게 가져오기 위해서 인접 리스트 형태로 그래프를 표현합니다.

var buildAdjList = function(edges) {
  const adjList = new Map();

  for (let [u, v] of edges) {
    if (!adjList.has(u)) {
    	adjList.set(u, { v: [], used: [] });
    }
    adjList.get(u).v.push(v);
  }
  
  for (let [key, value] of adjList) {
    value.used = new Array(value.v.length).fill(false);
  }
  
  return adjList;
}

주어지는 간선들(tickets)을 인접 리스트로 만들면서 한 가지 특이한 점은 used 배열이 인접 리스트의 각 아이템 요소로 생성된다는 것입니다. 이 used 배열은 이후, DFS 과정을 수행하면서 티켓이 사용되었는지 여부를 체크하기 위한 배열입니다.

 

다시 DFS로 돌아와서, DFS를 현재 문제에 맞게 재귀로 구현하면 다음과 같은 구조를 갖습니다.

function dfs(airline, departure, path, remainTicket){
    // 종료조건 1: 모든 티켓 사용
    if(remainTicket == 0) {
    	return path + " " + departure;
    }
    
    const possibleArrival = airline.get(departure);
    // 종료조건 2: 현재 도시에서 이동할 수 있는 도시가 없는 경우
    if (!possibleArrival) { return "ZZZZ"; }
    
    // 탐색
    let smallestPath = "ZZZZ";
    for(let i = 0; i < possibleArrival.v.length; i++) {
    	// 사용 가능한 티켓인지 체크
        if (possibleArrival.used[i]) {
            continue;
        }
        
        // 티켓 사용 체크
        possibleArrival.used[i] = true;
        // DFS 탐색
        const tmpPath = dfs(airline, possibleArrival.v[i], path + " " + departure, remainTicket-1);
        smallestPath = smallestPath > tmpPath ? tmpPath : smallestPath;
        // 티켓 사용 체크 해제
        possibleArrival.used[i] = false;
    }
    
    return smallestPath;
}

눈여겨봐야 할 점은 다음과 같습니다:

1. 두 개의 종료 조건
2. used 배열을 활용하여, 사용한 티켓 건너뛰기
3. 사용한 티켓 체크 및 해제
   • 사용한 티켓을 체크해줘야 티켓을 중복해서 사용하는 경우를 막을 수 있음
   • 해당 티켓 해제를 통해 또 다른 가능한 경로를 탐색할 때, 정상적으로 탐색할 수 있도록 해줘야 함

 

이제 위의 함수들을 활용하여 최종 메인 함수를 작성해보면 다음과 같습니다.

var findItinerary = function(tickets) {
    let answer = [];
    
    const n = tickets.length;
    const airline = buildAdjList(tickets);
    
    answer = dfs(airline, "JFK", "", n);
    
    return answer.trim().split(' ');
}

시간만 넉넉하다면, 현재의 코드로 올바른 답을 출력할 수 있습니다.

 

문제는 시간입니다. DFS를 이용하여 가능한 모든 여행경로를 찾는데, 기본적인 DFS 알고리즘은 노드를 기준으로 재귀 여부를 체크하기 때문에 $O(|V|+|E|)$의 시간 복잡도를 갖지만, 현재는 간선을 기준으로 하기 때문에 동일한 노드를 여러 번 반복할 수 있고, 그때마다 사용 가능한 에지만큼 반복하기 때문에 어림잡아 $O(E^V)$의 시간 복잡도가 걸립니다.

 

그래서 코드를 최적화하기 위해서 한 가지 쓸 수 있는 방법의 힌트는 출력해야 하는 정답이 리스트를 문자열로 볼 때, 사전 순으로 가장 작은 값이어야 한다는 것입니다.

 

DFS 안에 있는 반복문을 보면, 인접 리스트의 값을 순차적으로 탐색하고 있는데, 만약 이때 리스트의 값이 정렬되어 있다면? 어떻게 될까. 정렬되어 있다고 한다면, 처음으로 찾아지는 여행 경로가 찾을 수 있는 여행 경로 중 가장 작은 값이 될 것입니다. 이를 이용하면 탐색 과정을 가지치기할 수 있습니다.

 

정리하자면, 탐욕적인 방법으로 답을 찾고, 답이 찾아지면 가지치기를 통해 더 이상의 DFS 과정을 막는 것입니다.

 

이를 위해서 몇 가지 변경점이 있습니다.

• 인접 리스트에서 정렬된 리스트를 얻을 수 있도록 최초 입력으로 주어지는 배열을 도착지를 기준으로 정렬
• dfs()를 findItinerary()의 내부 함수로 정의 및 가지치기를 위한 조건문 작성

var findItinerary = function(tickets) {
    let answer = "";
    
    // 인접리스트가 정렬된 순서로 나올 수 있도록 tickets를 도착지를 기준으로 정렬
    tickets.sort((a, b) => a[1] > b[1] ? 1 : a[1] < b[1] ? -1 : 0);
    
    const n = tickets.length;
    const airline = buildAdjList(tickets);
    
    dfs(airline, "JFK", "", n);
    
    return answer.trim().split(' ');
    
    // 가지치기를 수행하기 위해 내부함수로 정의
    function dfs(airline, departure, path, remainTicket){
        if(remainTicket == 0) {
            answer = path + " " + departure;
            return;
        }

        const possibleArrival = airline.get(departure);
        if (!possibleArrival) { return; }

        for(let i = 0; i < possibleArrival.v.length; i++) {
            // 정답을 찾았을 시, 더 이상 탐색하지 않도록 break문을 걸어줌
            if (answer) { break; }
            if (possibleArrival.used[i]) {
                continue;
            }

            possibleArrival.used[i] = true;
            dfs(airline, possibleArrival.v[i], path + " " + departure, remainTicket-1);
            possibleArrival.used[i] = false;
        }

        return;
    }
}

빅오 표기법은 최악의 케이스를 가정하고 계산하기 때문에, 시간 복잡도 측면에서는 기존과 같을 수는 있습니다. 하지만, 실제 문제에서 최악 케이스에 도달하는 경우가 자주 있지는 않으므로, 대부분 탐색 중간에 정답을 찾고 문제에서 요구하는 기준 시간 내에 답을 찾게 됩니다.

 

Github: 332.js

GitHub - opwe37/Algorithm-Study