리트코드) 332. 일정 재구성(자바)

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

문제 : [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라.
여러 일정이 있는 경우 사전 어휘순으로 방문한다.

입력 : [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
출력 : [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]

1. 우선순위큐에 셋팅한다.(정렬되면서 저장된다)
2. DFS진행

import java.util.*;
class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> result = new ArrayList<>();

        // 경로map 셋팅
        Map<String, PriorityQueue<String>> locMap = new HashMap<String, PriorityQueue<String>>();
        for(int i=0; i<tickets.size(); i++) {
            String key = tickets.get(i).get(0);
            PriorityQueue<String> temp = new PriorityQueue<String>();
            if(locMap.containsKey(key)) {
                temp = locMap.get(key);
            }   
            temp.add(tickets.get(i).get(1));
            locMap.put(key, temp);        
        }

        dfs(result, locMap, "JFK"); // JFK에서 출발하는 여행 일정

        return result;
    }

    public void dfs(List<String> result, Map<String, PriorityQueue<String>> locMap, String from) {
        while(locMap.containsKey(from) && !locMap.get(from).isEmpty()) {
            dfs(result, locMap, locMap.get(from).poll()); // 여러 일정이 있는 경우 사전 어휘순으로 방문한다.(큐에서 꺼낸다) 
        }
        // 재귀가 모두 끝났다면 최종 위치는 도착지이므로 결과를 출발지까지 앞으로 삽입한다. (매우 중요)
        result.add(0, from);
    }
}