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

-Code

import java.util.*;

class Solution {
    static boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        // 경로가 2개 이상인 경우 알파벳 순임으로 정렬
        Arrays.sort(tickets, (o1, o2) -> {
            return o1[1].compareTo(o2[1]);
        });
        // 총 도시가 티켓수 +1 
        String[] answer = new String[tickets.length + 1];
        visited = new boolean[tickets.length];
        DFS(0, "ICN", answer, tickets);
        return answer;
    }
    
    private static boolean DFS(int depth, String city, String[] answer, String[][] tickets) {
        // answer 값 넣기
        answer[depth] = city;
        // answer가 다 입력되면 true (tickets.length가 answer의 마지막 idx)
        if (depth == tickets.length) {
            return true;
        }
        // 탐색
        for (int i = 0; i < tickets.length; i++) {
            // 현재 도시의 티켓이고 사용하지 않은 경우
            if (!visited[i] && tickets[i][0].equals(city)) {
                // 백트레킹 및 DFS
                visited[i] = true;
                if (DFS(depth + 1, tickets[i][1], answer, tickets)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        return false;
    }
}

정렬 문제와 DFS로 도는데 answer를 만드는데 티켓의 수 +1을 안 해주어서 이상하게 되었습니다. 또한 answer에 값을 넣어주는데 index관리도 문제가 있어서 여러 번 틀리다가 해당 부분에 대해서 문제가 있다는 것을 알게 되고 해결했습니다.