[프로그래머스][여행경로]-Lv.3

문제링크

🎃문제 설명

🎃제한 사항

🎃접근 방법

1. dfs를 통해 모든 경우의 수를 구한다.
2. Collections.sort를 이용해서 오름차순 정렬을 한다
3. 제일 처음 값을 return 형식에 맞게 return한다.

🎃코드

import java.util.*;
class Solution {
    static boolean[] visited;
    static ArrayList<String> answers;
    public String[] solution(String[][] tickets) {
        answers = new ArrayList<>();
        visited = new boolean[tickets.length];
        dfs(0, "ICN", "ICN", tickets);
        
        Collections.sort(answers);
        String[] answer = answers.get(0).split(" ");
        return answer;
    }
    static void dfs(int depth, String cur, String list, String[][] tickets){
        if(depth == tickets.length){
            answers.add(list);
            return;
        }
        for(int i=0; i<tickets.length; i++){
            if(!visited[i] && tickets[i][0].equals(cur)){
                visited[i] = true;
                dfs(depth+1, tickets[i][1], list+" "+ tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
}