[level3] 프로그래머스 - 여행경로(JAVA)

- "ICN"에서 출발하여, 
   모든 티켓을 다 사용하여,
   갈 수 있는 모든 경로를 ArrayList에 넣는다.

- 구한 경로를 알파벳순으로 정렬한 다음 맨 처음 것을 배열로 바꾸어 리턴한다.

 

 

import java.util.*;

class Solution {
    static boolean isVisited[];
    static ArrayList<String> answer;

    public static String[] solution(String[][] tickets) {
        answer = new ArrayList<String>();
        isVisited = new boolean[tickets.length];
        dfs(tickets, "ICN", "ICN", 1);
        Collections.sort(answer);

        return answer.get(0).split(" ");

    }

    private static void dfs(String[][] tickets, String route, String des, int cnt) {
        if (cnt == tickets.length + 1) {
            answer.add(route);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (!isVisited[i] && des.equals(tickets[i][0])) {
                isVisited[i] = true;
                dfs(tickets, route + " " + tickets[i][1], tickets[i][1], cnt + 1);
                isVisited[i] = false;
            }
        }
    }
}