Reconstruct Itinerary

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

Reconstruct Itinerary - LeetCode

 

주어진 티켓을 모두 사용해서 여행 계획을 짜는 문제이다. 이 때 완성된 여행 일정의 문자의 사전 순서가 빠른 순서인 것이 최종 정답이다.

 

문자의 속도가 중요하여 PriorityQueue를 이용해서 BFS를 처음에 시도했다. 하지만 시간 초과에 걸려 다른 방법들을 시도하다가 결국 정답 정보를 찾아보게 되었다. 사전 순서를 지키기 위해 PriorityQueue를 이용하고 DFS를 하는 방식이었다. 이 때 각 티켓, 사전 순으로 순환 하고 순환이 완료 된 이후에는 정답 리스트에 문자열을 추가한다.

 

PriorityQueue 에서 poll 하면서 순환하기 때문에 DFS 메서드에 최종 진입한 역은 다음 그래프가 없기 때문에 정답에 바로 추가 된다. 이처럼 메서드가 재귀적으로 역순 순환될 때 완료한 순서대로 정답이 추가된다. 이 때 역순으로 되기 때문에 addFirst 함수를 이용해서 역으로 정답에 담아 리턴 했다. 아래는 최종 통과 코드이다.

import java.util.*;  
  
public class Solution {  
  
    List<String> answer;  
  
    public List<String> findItinerary(List<List<String>> tickets) {  
  
        Map<String, PriorityQueue<String>> graphs = new HashMap<>();  
        answer = new ArrayList<>();  
  
        int ticketCnt = 0;  
        for(List<String> ticket: tickets){  
            String from = ticket.get(0);  
            String to = ticket.get(1);  
            if(!graphs.containsKey(from)){  
                graphs.put(from, new PriorityQueue<>());  
            }  
  
            graphs.get(from).add(to);  
        }  
  
        dfs("JFK", graphs);  
  
        return answer;  
    }  
  
    private void dfs(String airport, Map<String, PriorityQueue<String>> graphs){  
        PriorityQueue<String> graph = graphs.get(airport);  
        while(graph != null && !graph.isEmpty()){  
            dfs(graph.poll(), graphs);  
        }  
  
        answer.addFirst(airport);  
    }  
}