[Lv.3] 여행 경로 : Java

프로그래머스

 

주어진 항공권을 모두 사용해야함 > BFS보다 DFS 백트래킹이 더 효율적

 

목적지를 사전순으로 정렬하는 법

// 목적지를 사전순으로 정렬하기
        Arrays.sort(tickets, (a,b)-> {
            if(a[0].equals(b[0])) return a[1].compareTo(b[1]);
            return a[0].compareTo(b[0]);
        });

 

 

import java.util.*;

class Solution {
    static boolean[] visited;
    static List<String> route;
    static String[][] tickets;
    static boolean found = false;
    
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        visited = new boolean[tickets.length];
        route = new ArrayList<>();
        
        // 1) 티켓 정렬 (출발지 → 목적지 사전순)
        Arrays.sort(tickets, (a, b) -> {
            if (a[0].equals(b[0])) return a[1].compareTo(b[1]);
            return a[0].compareTo(b[0]);
        });
        
        // 2) "ICN"에서 시작
        route.add("ICN");
        dfs("ICN", 0);
        
        // 3) 리스트를 배열로 변환
        return route.toArray(new String[0]);
    }
    
    private void dfs(String start, int used) {
        if (found) return; // 이미 답 찾았으면 종료 (최초 경로가 사전순)
        
        if (used == tickets.length) {
            found = true;
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(start)) {
                visited[i] = true;
                route.add(tickets[i][1]);
                dfs(tickets[i][1], used + 1);
                if (found) return; // 정답 완성되면 더 안 탐색
                route.remove(route.size() - 1);
                visited[i] = false;
            }
        }
    }
}