문제 풀이(39)

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

import java.util.*;
import java.io.*;

class Solution {

    static boolean[] used;
    static int M;
    static ArrayList<String> ans = new ArrayList<>();
    public static void main(String[] args) {
       
        
        solution(new String[][]{
            {"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}
        });
    }

    public static String[] solution(String[][] tickets) {
        String[] answer = {};

        used = new boolean[tickets.length];

        M = tickets.length;

        Arrays.sort(tickets, new Comparator<String[]>() {
            
            @Override
            public int compare(String[] o1, String[] o2)
            {
                return o1[1].compareTo(o2[1]);
            }

        });

        dfs(0,"ICN", tickets,"ICN");

        Collections.sort(ans);

        answer = ans.get(0).split(" ");

        
        return answer;
    }

    public static void dfs(int k, String str, String[][] tickets, String start)
    {
        if (k == M) {
            ans.add(str);
            return;
        }else{

            for (int i = 0; i < tickets.length; i++) {
                
                if (tickets[i][0].equals(start)&&used[i] == false) {
                    used[i] = true;
                    dfs(k + 1, str+" "+tickets[i][1], tickets, tickets[i][1]);
                    used[i] = false;
                }
            }
        }
    }
}

dfs 메서드는 깊이 우선 탐색 알고리즘을 사용하여 가능한 경로를 찾는다. 이 메서드는 재귀적으로 호출된다.
현재 위치(start)에서 출발하는 항공권을 찾아서 사용 가능한 경우 (used[i]가 false이면) 해당 항공권을 사용한다.
다음 위치로 이동하고 재귀적으로 호출한다.
모든 항공권을 사용한 경우, 현재 경로를 ans 목록에 추가한다.
코드는 항공권을 사용하여 모든 가능한 경로를 찾고, 그 중 가장 사전 순으로 빠른 경로를 answer에 저장한 후 반환한다. 이렇게 하면 "ICN"에서 시작하여 모든 항공권을 사용하면서 가능한 경로를 찾을 수 있게 된다.