DFS + Map (PRO 여행경로)

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

---

문제 키워드

1. "알파벳 순서대로 저장" -> PriorityQueue (기본적으로 min heap)
2. "같은 출발지에 도착지가 여러 개" -> PQ를 값으로 담는 Map
3. "모든 도시를 방문" -> 완전탐색
4. "경로가 의미 있음" -> BFS가 아닌 DFS

 

 

import java.util.*;

class Solution {
    static Map<String, PriorityQueue<String>> map;
    static List<String> answer;
    
    public String[] solution(String[][] tickets) {
        // 1. 출발지 - 도착지"들" 짝지어 저장
        map = new HashMap<>();
        
        for (String[] t : tickets) {
            String key = t[0];
            String value = t[1];
            
            if(map.containsKey(key)) {
                PriorityQueue<String> pq = map.get(key);
                pq.add(value);
            } else {
                PriorityQueue<String> pq = new PriorityQueue<>();
                pq.add(value);
                map.put(key, pq);
            }
        }
        
        // 2. DFS를 활용해 경로 찾기
        answer = new ArrayList<>();
        dfs("ICN");
        
        // 3. 결과를 배열로 바꿔 반환
        return answer.toArray(new String[0]);
    }
    
    
    static void dfs(String cur) {
        while (map.containsKey(cur) && !map.get(cur).isEmpty()) {
            String next = map.get(cur).poll();
            dfs(next);
        }
        
        // 더이상 갈 곳이 없는 경우, 경로에 저장
        // [주의] DFS는 가장 끝까지 탐색한 후 백트래킹하여 돌아가므로, 경로를 역순으로 저장해야 최종 결과가 순서대로 나온다.
        answer.add(0, cur);
    }
}

 

참고 - Map

특징

1. `Map` 인터페이스는 키-값 쌍을 저장하며, 중복된 키는 허용되지 않습니다. 
2. `Map` 인터페이스는  세 가지 뷰(키 집합, 엔트리 집합, 값 컬렉션)를 제공합니다. 
3. `TreeMap`(Red-Black Tree로 구현)은 순서를 보장하지만 `HashMap`(Hash Table로 구현)은 순서를 보장하지 않습니다. 
4. 키로 사용하는 객체는 변경되지 않아야 하며, 변경 시 맵의 동작은 정의되지 않습니다. 
5. `Map`의 구현체들은 해시 코드와 `equals`를 사용하여 효율적으로 동작할 수 있습니다.

 

Map의 데이터를 추출하는 방법들 (= 3가지 뷰)

이 뷰들은 모두 Map과 연결되어 있어, 각각의 뷰를 통해 데이터를 수정하면 원래 Map에도 반영됩니다.

// 1. keySet(): 맵의 모든 키를 Set으로 반환.
for (String key : map.keySet()) {
    // 모든 키에 대해 반복 처리 가능
}

// 2. entrySet(): 맵의 모든 키-값 쌍을 Set으로 반환 (Map.Entry 타입의 Set).
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    // 키와 값을 동시에 접근 가능해 성능 향상됨
}

// 3. values(): 맵의 모든 값들을 Collection으로 반환.
for (Integer value : map.values()) {
    // 모든 값에 대해 반복 처리 가능
}

 

Map의 주요 메서드

// 1. get(Object key): 주어진 키에 해당하는 값을 반환. 키가 없으면 null을 반환.
Integer value = map.get("key");

// 2. put(K key, V value): 주어진 키와 값을 맵에 추가. 키가 이미 존재하면 기존 값을 덮어씀.
map.put("key", 100);

// 3. containsKey(Object key): 맵에 특정 키가 존재하는지 여부를 확인.
if (map.containsKey("key")) {
    // do something
}

// 4. remove(Object key): 주어진 키에 해당하는 엔트리를 맵에서 제거.
map.remove("key");

// 5. size(): 맵에 들어있는 엔트리(키-값 쌍)의 개수를 반환.
int size = map.size();