Lv 3. 여행경로

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

프로그래머스

 

 

이 문제는 DFS를 사용해 주어진 항공권 목록을 통해 모든 가능한 경로를 찾고,

알파벳 순서상 가장 빠른 경로를 반환하는 문제다.

 

먼저 dfs 메서드를 통해 "ICN"에서 출발하여 다음 공항으로

이동하는 재귀적 탐색을 진행하며,

방문한 항공권은 isVisited 배열로 관리해 중복 방문을 방지하고,

routes 리스트에 경로가 완성될 때마다 추가한다.

 

dfs는 현재 공항과 경로, 그리고 몇 개의 티켓을 사용했는지를

매개변수로 받아 모든 항공권을 사용해 가능한 경로를 찾을 때까지

재귀적으로 호출하며,

탐색이 끝나면 방문한 항공권의 isVisited 값을 다시 false로 초기화해

백트래킹을 수행한다.

 

모든 경로 탐색이 완료되면 routes 리스트를 알파벳 순서로 정렬하고

가장 첫 번째 경로를 선택해 이를 정답으로 반환하며,

정답은 공백을 기준으로 분리해 문자열 배열로 만들어 반환한다.

 

이 코드의 특징은 DFS와 백트래킹을 통해 가능한 모든 경로를 찾고

최적 경로를 구하는 방식으로, 탐색이 깊어질수록 경로를 재탐색하면서

각 항공권을 한 번씩 사용하도록 설정해 최단 경로를 선택할 수 있게 했다.

 

 

 

import java.util.*;

class Solution {
    boolean[] isVisited;
    ArrayList<String> routes;
    private void dfs(String now, String route, String[][] tickets ,int cnt){
        if(cnt > tickets.length){
            routes.add(route);
            return;
        }
        for(int i = 0 ; i < tickets.length ; i++){
            if(now.equals(tickets[i][0]) && !isVisited[i]){
                isVisited[i] = true;
                dfs(tickets[i][1],route+" "+tickets[i][1],tickets,cnt+1);
                isVisited[i] = false;
            }
        }
    }
    public String[] solution(String[][] tickets) {
        String[] answer;
        isVisited = new boolean[tickets.length];
        routes = new ArrayList<>();
        int cnt = 0;
        
        dfs("ICN","ICN",tickets,cnt+1);
        
        Collections.sort(routes);
        answer = routes.get(0).split(" ");
        return answer;
    }
}