programmers_여행경로_java

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

프로그래머스

import java.util.*;

class Solution {
    
    public static List<String> answerList;
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        answerList = new ArrayList<>();
        
        boolean[] visited = new boolean[tickets.length];
        dfs(0, "ICN", tickets, tickets.length, visited, "ICN");
        
        Collections.sort(answerList); // 정답이 될수 있는것 정렬
        
        answer = answerList.get(0).split(" ");
        return answer;
    }
    
    public void dfs(int cnt, String now, String[][] tickets, int ticketsSize, boolean[] visited, String ans){
        if(cnt == tickets.length){ // 모든 티켓 탐색 완료
            answerList.add(ans);
            return;
        }
        
        for(int i = 0; i<ticketsSize; i++){
            if(!visited[i] && tickets[i][0].equals(now)){
                visited[i] = true;
                dfs(cnt+1, tickets[i][1], tickets,ticketsSize, visited, ans+" "+tickets[i][1]);
                visited[i] = false;
            }
        }
    }
}