99클럽 코테 스터디 34일차 TIL / [프로그래머스] 여행경로

오늘의 학습 키워드

---

DFS

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/43164

• 플랫폼: 프로그래머스
• 문제명: 여행경로
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    
    static Map<String, PriorityQueue<String>> fromToMap = new HashMap<>();
    static List<String> ansList = new LinkedList<>();
    
    public String[] solution(String[][] tickets) {
        for(String[] ticket : tickets) {
            fromToMap.putIfAbsent(ticket[0], new PriorityQueue<>());
            fromToMap.get(ticket[0]).add(ticket[1]);
        }
        
        dfs("ICN");
        
        return ansList.toArray(new String[ansList.size()]);
    }
    
    public void dfs(String from) {
        while(fromToMap.containsKey(from) && !fromToMap.get(from).isEmpty()) {
            String to = fromToMap.get(from).poll();
            dfs(to);
        }
        
        ansList.add(0, from);
    }
}

접근

• 항공권에 대한 정보를 담을 fromToMap을 만들었습니다.
  • 가능한 경로가 여러 개일 경우, 알파벳 순서가 앞서는 경로부터 탐색해야 하므로 value에는 PriorityQueue를 활용했습니다.

    for(String[] ticket : tickets) {
        fromToMap.putIfAbsent(ticket[0], new PriorityQueue<>());
        fromToMap.get(ticket[0]).add(ticket[1]);
    }

• 모든 도시를 방문할 수 없는 경우는 주어지지 않기 때문에, 항공권의 개수만큼 탐색이 이루어지면 됩니다.
  • 하지만 단순히 출발지부터 알파벳 순으로 방문하여 ansList에 정답을 추가하게 될 경우 반례가 존재하게 됩니다.
    • 반례
      • input: [["ICN", "D"], ["D", "ICN"], ["ICN", "B"]]인 경우, 알파벳 순서대로 B를 먼저 방문하게 될 경우 D를 방문할 수 없게 됩니다.
  • 경우를 모두 따져서 반례를 걸러낼 수도 있지만, 알파벳 순으로 탐색을 모두 진행한 뒤 현재 위치를 ansList의 가장 앞에 삽입을 하게되면 가장 먼저 삽입한 값은 최종 도착지가 되고, 결과적으로 항공권의 개수만큼만 탐색을 진행하면서 올바른 경로를 도출할 수 있습니다. (ansList의 가장 앞단에 값을 삽입할 때 O(1)에 처리하기 위해 List의 구현체를 LinkedList로 사용했습니다.)

    public void dfs(String from) {
        while(fromToMap.containsKey(from) && !fromToMap.get(from).isEmpty()) {
            String to = fromToMap.get(from).poll();
            dfs(to);
        }
        
        ansList.add(0, from);
    }

    • 위 반례를 따라가보면 다음과 같습니다.
      1. ICN → B
      2. B (add) // ansList: B
      3. ICN → D
      4. D → ICN
      5. ICN (add) // ansList: ICN → B
      6. D (add) // ansList: D → ICN → B
      7. ICN (add) // ansList: ICN → D → ICN → B

소요 시간

30분