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

문제 소개

오늘 풀었던 여행경로 - 프로그래머스 문제를 정리합니다.
이 문제는 모든 항공권을 한 번씩 사용하면서 사전순으로 가장 앞선 여행 경로를 찾는 문제입니다.
문제의 핵심은 "모든 티켓 사용 여부 우선"과 "여러 경로 중 사전순으로 앞선 경로 선택"에 있습니다.

문제 링크: 여행경로 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 티켓 정보를 출발지 → 도착지 형태의 그래프로 변환
2. 각 출발지의 도착지 리스트는 사전순 정렬 (우선 방문을 위한 사전순 처리)
3. DFS로 가능한 경로를 따라가며, 티켓을 모두 사용한 경우 경로 확정

---

해결 과정 및 코드

핵심 아이디어

1. 티켓을 HashMap<String, List<Airport>> 형태로 구성하여 출발지 기준 도착지 리스트 관리
2. 도착지 리스트는 사전순 정렬 → 여러 경로 중 알파벳 앞선 경로 우선 탐색
3. DFS로 가능한 경로를 따라가며 isArrived 플래그로 티켓 사용 여부 관리
4. 티켓을 모두 사용하는 경로만 유효 → 이 조건을 만족하는 경로만 반환
5. 알파벳 순서 고려는 티켓 전부 사용 가능한 경로에서만 적용
6. 도착지만 있는 공항에서 airports.get 시 NullPointerException 발생
   → getOrDefault로 대체하여 예외 방지

코드

시간 복잡도 : O(N^2) ( N 깊이 * N 후보 )

import java.util.*;

class Solution {
    class Airport implements Comparable<Airport> {
        String name;
        boolean isArrived;

        Airport(String name) {
            this.name = name;
            this.isArrived = false;
        }

        @Override
        public int compareTo(Airport other) {
            return this.name.compareTo(other.name);
        }
    }
    
    // 티켓 출발지 : 도착지s 나타내는 맵
    static HashMap<String, ArrayList<Airport>> airports;
    public String[] solution(String[][] tickets) {
        airports = new HashMap<>();

        for (String[] ticket : tickets) {
                     // 첫 출발 공항일 경우 List 추가
            airports.computeIfAbsent(ticket[0], k -> new ArrayList<>())
                    // ticket[0] -> 도착지 공항 추가
                    .add(new Airport(ticket[1]));
        }
		
        // 사전순 정렬 (우선 탐색)
        for (String key : airports.keySet()) {
            Collections.sort(airports.get(key));
        }
        String[] ans = new String[tickets.length + 1];
        ans[0] = "ICN";
        dfs(1, ans);
        return ans;
    }

    boolean dfs(int depth, String[] visited) {
        if (depth == visited.length) { // 모든 공항 방문 성공
            return true;
        }
        
        // 출발지로 되지 않은 공항일 경우 대비 getOrDefault
        for (Airport des : airports.getOrDefault(visited[depth - 1], new ArrayList<>())) {
            if (des.isArrived) continue;
            des.isArrived = true;
            visited[depth] = des.name;
            if (dfs(depth + 1, visited)) return true;
            des.isArrived = false;
        }

        return false;
    }
}