[프로그래머스: DFS] 여행경로

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

프로그래머스

 

# DFS 코드

import java.util.*;

class Solution {
    List<String> route = new ArrayList<>(); // 최종 정답 경로를 저장할 ArrayList
    Map<String, PriorityQueue<String>> map = new HashMap<>(); // 출발지 → 도착지를 저장할 map (알파벳 순 정렬 위해 우선순위 큐 사용)

    public String[] solution(String[][] tickets) {
        for (String[] ticket : tickets) {
            String from = ticket[0]; // 출발지
            String to = ticket[1];   // 도착지

            map.putIfAbsent(from, new PriorityQueue<>()); // 출발지가 처음 등장했다면 value로 우선순위 큐 생성
            map.get(from).offer(to); // 출발지(key)에 해당하는 value 큐에 도착지 추가
        }
        
        dfs("ICN");

        // List<String> → String[] 변환
        return route.toArray(new String[0]);
    }

    // DFS 함수
    public void dfs(String airport) {
        PriorityQueue<String> pq = map.get(airport);

        // 갈 수 있는 도착지가 더 이상 없을 때까지 반복
        while (pq != null && !pq.isEmpty()) {
            String next = pq.poll(); // 알파벳 순으로 가장 빠른 공항부터 꺼냄
            dfs(next);               // 다음 공항으로 재귀 탐색
        }

        route.add(0, airport); // 경로를 역순으로 저장
    }
}

• PriorityQueue(우선순위 큐)를 사용하면 DFS가 사전순으로 빠른 경로부터 먼저 탐색하게 된다. 그렇기 때문에 정답 경로가 여러 개더라도 제일 먼저 찾는 경로가 가장 사전순으로 빠른 정답이 되게 된다.
• 또한 티켓을 다 사용하고 탐색이 끝난 그 순간부터 돌아오면서 경로를 저장해야 하는데, 그 이유는 DFS는 티켓을 다 쓴 시점에만 정답이 확정되기 때문이다. 그래서 'add(0, 공항)'을 이용해 경로를 거꾸로 쌓아 정답 경로를 도출한다. (후위 순회(post-order) 방식)
• [갈 수 있는 도착지가 더 이상 없을 때까지 반복]
  • pq != null : 이 공항에서 갈 수 있는 도착지 리스트가 존재하고 (모든 공항이 출발지로만 등장하는 것은 아니기 때문. 어떤 공항은 목적지로만 등장할 수도 있음)
  • !pq.isEmpty() : 갈 수 있는 도착지가 아직 남아 있어야 함

 

 

 

+ 주석폭발코드

import java.util.*;

class Solution {
    List<String> route = new ArrayList<>(); // 최종 정답 경로를 저장할 ArrayList
    Map<String, PriorityQueue<String>> map = new HashMap<>(); // 출발지 → 도착지를 저장할 map (알파벳 순 정렬 위해 우선순위 큐 사용)

    public String[] solution(String[][] tickets) {
        // tickets의 모든 요소를 하나씩 돌며 map 구성
        for (String[] ticket : tickets) {
            String from = ticket[0]; // 출발 공항
            String to = ticket[1];   // 도착 공항

            // 출발지가 처음 등장했다면 우선순위 큐 생성 (자동으로 알파벳 순 정렬됨)
            // putIfAbsent(key, value) : 해당 key가 존재하지 않으면 value를 넣고, 이미 존재하면 아무것도 하지 않는다.
            map.putIfAbsent(from, new PriorityQueue<>());

            // map.get(from) : 출발지에 해당하는 도착지 목록(우선순위 큐)을 가져와서
            // .offer(to) : 해당 큐에 도착지를 추가
            map.get(from).offer(to);
        }
        
        dfs("ICN"); // 항상 ICN 공항에서 출발

        // 리스트를 배열로 변환해서 정답 리턴
        // List<String> → String[]
        return route.toArray(new String[0]); // new String[0]은 String[] 타입으로 정확히 변환하기 위해 필요한 빈 배열
    }

    // DFS 함수: 도착지를 하나씩 꺼내며 깊이 탐색
    public void dfs(String airport) {
        // 출발지(=airport)에서 갈 수 있는 도착지 목록 pq
        PriorityQueue<String> pq = map.get(airport);

        // 갈 수 있는 도착지가 더 이상 없을 때까지 반복
        while (pq != null && !pq.isEmpty()) {
            String next = pq.poll(); // 알파벳 순으로 가장 빠른 공항부터 꺼냄
            dfs(next);               // 다음 공항으로 재귀 탐색
        }

        // 티켓을 다 사용하고 탐색이 끝난 그 순간부터 돌아오면서 경로를 저장해야 함!
        route.add(0, airport); // 경로를 역순으로 저장
    }
}