프로그래머스 여행경로

문제

풀이

주어진 모든 항공권을 사용해야 하는 조건이 있기 때문에 완전탐색 진행
모든 경로를 구해주고 정렬을 해서 알파벳 순 가장 빠른 경로 리턴

코드

import java.util.*;
class Solution {
    static ArrayList<String> list = new ArrayList<>();
    static boolean v[];

    public String[] solution(String[][] tickets) {
        v = new boolean[tickets.length];

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

        Collections.sort(list);

        return list.get(0).split(" ");
    }

    static void dfs(int depth, String now, String path, String[][] tickets){
        if (depth == tickets.length) {
            list.add(path);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (!v[i] && now.equals(tickets[i][0])) {
                v[i] = true;
                dfs(depth+1, tickets[i][1], path + " " +tickets[i][1], tickets);
                v[i] = false;
            }
        }
    }
}

#dfs