[프로그래머스] 여행경로 / JAVA

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

import java.util.*;
class Solution {
    public static boolean selected[];
    public static boolean isEnd;
    public static String[][] ticket;
    public static int N;
    public static String[] ans;
    public static void dfs(String start, Stack<String> visited,int cnt){
        if(cnt==N){
            isEnd = true;
            ans = new String[visited.size()];
            int idx = 0;
            while(!visited.isEmpty()){
                ans[idx++] = visited.pop();
            }

            return;
        }
        if(isEnd) return;
        for(int i=0;i<N;i++){
            if(start.equals(ticket[i][0])){
                if(selected[i]) continue;
                selected[i] = true;
                visited.add(ticket[i][1]);
                if(isEnd) return;
                dfs(ticket[i][1],visited,cnt+1);
                if(isEnd) return;
                selected[i] = false;
                visited.pop();
            }
        }
    }
    public static String[] solution(String[][]tickets){
        HashSet<String> cnt = new HashSet<String>();
        for(int i=0;i<tickets.length;i++){
            for(int j=0;j<tickets[i].length;j++){
                cnt.add(tickets[i][j]);
            }
        }
        N = tickets.length;

        Arrays.sort(tickets, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                if(o1[0].equals(o2[0])){
                    return o1[1].compareTo(o2[1]);
                }else{
                    return o1[0].compareTo(o2[0]);
                }
            }
        });
        selected = new boolean[tickets.length];
        ticket = new String[tickets.length][tickets[0].length];
        Stack<String> visited = new Stack<String>();
        for(int i=0;i<N;i++){
            for(int j=0;j<2;j++){
                ticket[i][j] = tickets[i][j];
            }
        }
        visited.add("ICN");
        dfs("ICN",visited,0);
        String [] realAns = new String[ans.length];
        for(int i=0;i<ans.length;i++){
            realAns[i] = ans[ans.length-i-1];
        }
        return realAns;
    }
}