[자바 알고리즘 인터뷰] 12장 그래프 (7) 일정 재구성

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

 

 

 

 

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

 

 

풀이 1) 일정 그래프 재귀  DFS

 

- 여행 일정을 그래프로 구성해 DFS를 진행하면 징행된 경로를 정답으로 처리할 수 있다. 

- 주의할 점은 중복된 일정일 경우 어휘순으로 방문한다는 점이다, 

- 입력값인 여행 일정은 끝까지 이어질 것이므로 from->to 형태의 그래프로 구성해 끝까지 탐색하면 된다. 

 

//여행 일정을 from->to 형태의 그래프로 구성
for(List<String> ticket : tickets) {
    //값이 존재하지 않을 경우 빈 우선순위 큐 생성
    fromToMap.putIfAbsent(ticket.get(0), new PriorityQueue<>());
    //목적지 to 추가, 우선순위 큐이므로 to는 항상 사전 어휘순으로 정렬된다. 
    fromToMap.get(ticket.get(0)).add(ticket.get(1));
}

 

- 어휘순으로 방문해야 하기 때문에 그래프를 구성할 때 우선순위 큐를 사용했다. 

- 이렇게 하면 입력값이 무작위로 들어온다고 해도 사전순으로 계속 정렬되어 저장될 것이다. 

- 도착지 to 목록은 우선순위 큐이기 때문에 정렬된 상태로 저장된다. 

ex)

{
    ICN = [ATL],
    ATL = [ICN,JFK],
    JFK = [ATL,ICN]
}

 

 

public void dfs(List<String>results, Map<String,PriorityQueue<String>> fromToMap, String from)
    {
        //from->to 값이 존재하는 경우 반복해서 재귀 dfs
        while(fromToMap.containsKey(from)&&!fromToMap.get(from).isEmpty())
        {
            //사전 어휘순 첫 위치부터 우선순위 큐를 이용해 추출 및 재귀 dfs 진행
            dfs(results, fromToMap, fromToMap.get(from).poll());
        }

        //재귀 dfs가 모두 끝났다면 최종 위치는 도착지이므로 결과를 출발지까지 앞으로 삽입한다. 
        results.add(0,from);
    }

 

- 출발지 from에 값이 존재하는 경우 계속 반복하면서 사전 어휘순으로 DFS를 진행한다. 

- 우선순위 큐이므로 한 번 꺼낸 경로는 사라져 재방문하지 않을 것이며, 어떤 경우든 여행 일정은 도착지까지 이어질 것이므로 이대로 탐색하다 보면 도착지에 무사히 도달할 것이다. 

 

- 결과 변수 results에 add()를 할 때 인덱스 0을 지정해 맨 앞에 값을 삽입 

  - >DFS를 모두 진행하고 되돌아왔을 때 해당 위치를 결과에 삽입하게 되며 가장 먼저 삽입하게 될 위치는 최종 위치인 도착지이므로, 출발지까지 결과를 차례대로 앞으로 삽입하게 된다. 

 

 

 

class Solution {
    public void dfs(List<String>results, Map<String,PriorityQueue<String>> fromToMap, String from)
    {
        //from->to 값이 존재하는 경우 반복해서 재귀 dfs
        while(fromToMap.containsKey(from)&&!fromToMap.get(from).isEmpty())
        {
            //사전 어휘순 첫 위치부터 우선순위 큐를 이용해 추출 및 재귀 dfs 진행
            dfs(results, fromToMap, fromToMap.get(from).poll());
        }

        //재귀 dfs가 모두 끝났다면 최종 위치는 도착지이므로 결과를 출발지까지 앞으로 삽입한다. 
        results.add(0,from);
    }
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> results = new LinkedList<>();
        Map<String, PriorityQueue<String>> fromToMap = new HashMap<>();

        //여행 일정을 from->to 형태의 그래프로 구성
        for(List<String> ticket : tickets) {
            //값이 존재하지 않을 경우 빈 우선순위 큐 생성
            fromToMap.putIfAbsent(ticket.get(0), new PriorityQueue<>());
            //목적지 to 추가, 우선순위 큐이므로 to는 항상 사전 어휘순으로 정렬된다. 
            fromToMap.get(ticket.get(0)).add(ticket.get(1));
        }

        //재귀 dfs 시작
        dfs(results, fromToMap, "JFK");

        return results;
    }
}

7밀리초 

 

 

풀이 2) 일정 그래프 반복 DFS

 

- DFS는 재귀뿐만 아니라 반복으로도 풀이할 수 있다. 

- DFS를 반복 구조로 구현할 때는 스택을 사용한다. 

 

- 출발지는 항상 JFK이므로 가장 먼저 JFK가 오게 되고, JFK가 스택에 들어갔다가 다음 도착지로 ATL과 ICN 중 어휘순에 따라 ATL을 먼저 방문한다. 

- 다시 ATL이 스택에 들어갔다가 다음 도착지로 ICN과 JFK중 ICN을 먼저 방문하고, ATL과 JFK를 거쳐 남아 있는 방문지인 ICN으로 향한다. 

- 한 번 방문했던 곳은 우선순위 큐로 구현된 그래프에서 끄집어내며, 일정에서 사라지므로 더 이상 방문하지 않게 된다. 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자: 박상길 <책만>

 

//출발지 삽입
 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());
 }

 

- 스택에 삽입하며, 스택에서 추출된 값을 출발지로 하여 도착지를 계속해서 스택에 삽입한다. 

- 마지막으로 스택에 쌓인 경로를 하나씩 추출해서 앞쪽으로 쌓게 되면, 즉 순서를 뒤집으면 원래의 여행 경로가 된다. 

 

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

        //여행 일정을 from->to 형태의 그래프로 구성
        for(List<String> ticket : tickets) {
            //값이 존재하지 않을 경우 빈 우선순위 큐 생성
            fromToMap.putIfAbsent(ticket.get(0), new PriorityQueue<>());
            //목적지 to 추가, 우선순위 큐이므로 to는 항상 사전 어휘순으로 정렬된다. 
            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;
    }
}

7밀리초