[leetcode 332] Reconstruct Itinerary

내가 이 문제를 푼 적이 있었다니 전혀 기억이.. 문제 난이도는 hard이다. 다시 풀어도 또 못 풀꺼 같다. 

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

Reconstruct Itinerary - LeetCode

 

문제 요약:

tickets[i] = [from(i), to(i)] 티켓은 from, to 도시가 적혀있는 배열이다. 한 남자가 'JFK'에서 출발하여 모든 path를 한 붓 그리기로 방문한다. 이 때 방문한 경로를 리턴하라. 방문 경로가 여러 개라면 lexical order가 가장 작은 것을 리턴한다. 

 

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. 랜덤한 vertex에서 시작하여 사용하지 않은 edge를 탐색한다. 언제? 갈 곳이 없을 때까지(=더 이상 unvisited outgoing edge가 없는 vertex에 이를 때까지)

2. 현재 path에서 unused edge가 있는 가장 가까운 vertex로 backtracking한다. 모든 edge를 방문할 때 까지 스탭1을 진행한다. 

 

 

1. path를 저장하기 위한 자료구조

edge 사용여부를 체크해야 하고 lexical order를 따져야 하므로 한 vertex에 연결된 vertex 리스트를 표현하기 위해 map과 priority queue를 사용한다. 도시 이름을 key로 하여 priority queue를 adjacent list로 사용한다.

 

2. dfs + backtracking

stack을 사용하여 경로를 체크한다. vertex를 방문할 때 마다 stack에 push하여 더 이상 갈 때가 없을 때까지 진행한다.

만약 더 이상 갈 때가 없다면 stack에서 pop한다.

더 이상 갈 때가 없는 것은 priority queue로 판단한다. 다음 vertex로 이동 시 priority queue에서 다음 노드를 찾은 후 pop시킨다. priority queue가 비었다면 더 이상 갈 곳이 없는 것이다. 

 

public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> mp = new HashMap<>();
        for(List<String> ticket: tickets){
        // 리스트 초기화
            mp.computeIfAbsent(ticket.get(0), k-> new PriorityQueue<>()).add(ticket.get(1));
        }
        
        List<String> route = new ArrayList<>();
        Deque<String> stk = new ArrayDeque<>();
        
        stk.push("JFK");
        while(!stk.isEmpty()){
            
            // 더 이상 갈 때가 없을 때까지 push
            while(mp.containsKey(stk.peek()) && !mp.get(stk.peek()).isEmpty()){
                stk.push(mp.get(stk.peek()).poll());
            }
            
            // unused edge가 있는 vertex가 나올 때까지 pop
            route.add(0, stk.pop());
        }
        
        return route;
    }