[Leetcode 332] 여정 재구성 - DFS, 우선순위 큐

https://leetcode.com/problems/reconstruct-itinerary/description/

Reconstruct Itinerary - LeetCode

 

Problems

티켓[i] = [출발지, 도착지]가 한 항공편의 출발 및 도착 공항을 나타내는 항공권 목록이 주어집니다. 여정을 순서대로 재구성하여 반환합니다.

모든 항공권은 여정이 "JFK"로 시작해야 합니다. 유효한 여정이 여러 개 있는 경우 단일 문자열로 읽었을 때 어휘 순서가 가장 작은 여정을 반환해야 합니다.

예를 들어, 여정 ["JFK", "LGA"]는 ["JFK", "LGB"]보다 어휘 순서가 더 작습니다.
모든 항공권이 하나 이상의 유효한 여정을 구성한다고 가정할 수 있습니다. 모든 항공권은 한 번만 사용해야 합니다.

 

입력 및 출력 값

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"]

 

---

전략 1. 재귀를 이용한 DFS

 

모든 항공권의 경로를 먼저 Map에 등록한다. 이때 DFS를 이용해서 출발지에 대한 도착지가 여러 곳이 존재할 경우 어휘순으로 가장 작은 도착지를 뽑아야 하는데 우선순위 큐를 이용해서 빼도록 하면 된다. Map<String,PriorityQueue<String>> pathMap = new HashMap<>();

 

DFS는 "JFK"로 시작되며 결과를 바로 집어넣는 대신에 먼저 재귀를 통해 경로의 끝까지 간 다음에 (한번 간 경로는 poll()을 이용해 빼준다) result.add(0,path); 로 뒤에서부터 추가한다. 이렇게 하면 조금 더 깔끔한 풀이가 가능해보인다.

public List<String> findItinerary(List<List<String>> tickets) {
    List<String> result = new LinkedList<>();
    Map<String, PriorityQueue<String>> pathMap = new HashMap<>();
    for (List<String> ticket : tickets) {
        pathMap.putIfAbsent(ticket.get(0), new PriorityQueue<>());
        pathMap.get(ticket.get(0)).add(ticket.get(1));
    }
    dfs(result, "JFK", pathMap);

    return result;
}

private void dfs(List<String> result, String path, Map<String, PriorityQueue<String>> pathMap) {

    //from -> to 값이 존재하는 경우 반복해서 재귀 DFS
    while (pathMap.containsKey(path) && !pathMap.get(path).isEmpty()) {
        dfs(result, pathMap.get(path).poll(), pathMap);
    }
    result.add(0, path);

}

 

 

---

전략 2. 스택을 이용한 DFS

본 풀이도 위와 크게 달라진 점은 없지만 재귀가 아닌 반복문으로 풀이가 가능하다. 이로써 좀더 직관적인 풀이가 가능하고 성능상 재귀보다는 조금 더 빠르다. 하지만 문제에는 재귀로만 풀 수 있는 문제가 자주 나오니 주의해야 한다.

 

풀때 Deque 인터페이스인 ArrayDeque구현체의 메서드가 헷갈렸다. 다른 분의 글에서 정리가 되었으니 참고해야겠다.

스택을 사용하여 JFK으로 시작한 출발지를 먼저 넣고 그에 대하는 목적지로 계속 나아간다.  그다음 앞 풀이 처럼 결과는 나중에 처리하는 방식으로 풀이를 하였다.

 

public List<String> findItinerary1(List<List<String>> tickets) {
    Map<String, PriorityQueue<String>> fromToMap = new HashMap<>();

    for (List<String> ticket : tickets) {
        fromToMap.putIfAbsent(ticket.get(0), new PriorityQueue<>());
        fromToMap.get(ticket.get(0)).add(ticket.get(1));
    }
    List<String> results = new LinkedList<>();
    Deque<String> stack = new ArrayDeque<>();

    stack.push("JFK");
    while (!stack.isEmpty()) {
        while (fromToMap.containsKey(stack.getFirst()) && !fromToMap.get(stack.getFirst()).isEmpty()) {
            stack.push(fromToMap.get(stack.getFirst()).poll());

        }
        results.add(0, stack.pop());
    }
    return results;
}

 

 

번외. 인자 타입이 다른 경우

프로그래머스에서도 비슷한 문제가 있다. 거의 다 똑같지만 반환타입과 인자타입이 배열형태인데 거기에만 주목해보자.

public String[] solution(String[][] tickets) {
    Map<String,PriorityQueue<String>> map = new HashMap<>();
    for(String[] ticket: tickets){
        map.putIfAbsent(ticket[0],new PriorityQueue<>());
        map.get(ticket[0]).add(ticket[1]);
    }
    List<String> result = new LinkedList<>();
    dfs(map, "ICN", result);
    return result.toArray(new String[0]);
}

private void dfs(Map<String,PriorityQueue<String>> map, String st, List<String> result){
    while(map.containsKey(st) && !map.get(st).isEmpty()){
        dfs(map, map.get(st).poll(), result);
    }
    result.add(0,st);
}