[알고리즘] Leetcode_332_Reconstruct_Itinerary

Problem

Solve

• 항공권의 출발지와 목적지를 graph로 정리해주기위해 Map 을 이용한다. 여기서 목적지가 여러 개일 경우 lexical order 로 정렬된 채로 저장하기위해 우선순위큐 PriorityQueue 를 이용한다.
• 항공권 정보를 정리된 graog 를 가지고 dfs 순회를 한다. 출발지에서 도착할 수 있는 가능한 도착지를 계속 방문하는 방식으로 구현한다.
• DFS로 순회하면서 더이상 갈 목적지가 없다면 그 때의 출발지를 결과값 answer에 추가해주고 백트래킹을 한다.
• 첫 방문지까지 answer에 마지막에 추가가 됨으로써 백트래킹과 DFS 재귀 순회는 마무리가 되고 answer는 출발지와 도착지가 거꾸로 정렬이 되어있기 때문에 Collections.reverse() 를 이용해 다시 정렬을 해준 후 반환한다.

import java.util.*;
class Solution {
    public void backtracking(Map<String, PriorityQueue<String>> graph, String airport, List<String> answer){

        PriorityQueue<String> destinations = graph.get(airport);
        
        while(destinations != null &&!destinations.isEmpty()){
            String next = destinations.poll();
            backtracking(graph, next, answer);
        }
        answer.add(airport);
        
    }
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();

        for(List<String> ticket : tickets){
            String departure = ticket.get(0);
            String arrival = ticket.get(1);
            if(!graph.containsKey(departure)){
                graph.put(departure, new PriorityQueue<>());
            }
            graph.get(departure).offer(arrival);
        }
        List<String> answer = new ArrayList<>();
        backtracking(graph, "JFK",  answer);
        
        Collections.reverse(answer);
        return answer;
    }
}

• 어려웠던 점은 항공권 정보를 저장할 때 처음에 우선순위큐가 아닌 리스트로 정렬을 한 상태였는데, 이를 정렬하기가 까다로웠다. 물론 코드로는 할 수는 있을 것 같다. 좀 시간이 걸리겠지만,,,
• 아무튼 백트래킹이 문제이고 while문이나 다시 돌아가야할 때 어떤 코드를 작성해야할 지 아직 어렵게 느껴진다.
• 그리고 answer에 추가해주는 문자열의 순서를 backtracking 전에 재귀를 시작할 때 추가해주면 왜 안되는지 모르겠다. 이는 더 공부해야할 것이다.