DFS - 여행경로

프로그래머스 (DFS) - 여행경로

해당 문제는 DFS 관련 문제로 보입니다. 하나의 시작 공항으로 부터 관련 티켓 정보를 통해 하나씩 연결해 가며 최종 티켓 깊이 까지 도달하게 되면 그때까지의 path 정보를 리스트에 넣어주는 방식으로 구현했습니다. 문제에서 최종 경로를 다 구한 후에는 알파벳 순서가 앞서는것 1개를 return 해달라고 했으므로 최종적으로 정렬 후 첫번째 path 정보를 split 하여 요구사항에 맞게 답을 return 하였습니다.

private boolean[] used;
    private List<String> paths;

    public String[] solution(String[][] tickets) {
        used = new boolean[tickets.length];
        paths = new ArrayList<>();
        dfs(0, "ICN", "ICN", tickets);
        Collections.sort(paths);
        String[] answer = paths.get(0).split(",");
        return answer;
    }

    private void dfs(int depth, String airportName, String path, String[][] tickets) {
        if (depth == tickets.length) {
            paths.add(path);
            return;
        }

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