[프로그래머스 알고리즘 고득점 Kit][깊이/너비 우선 탐색(DFS/BFS)][Java] 여행경로

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

프로그래머스

백트래킹으로 접근했습니다.

티켓으로 도착한 곳의 출발지가 같은 티켓을 사전순으로 접근하면서
가장 먼저 n개의 티켓을 사용한 경로를 반환.

알파벳 순이 먼저인 경로를 반환하라고 명시되어 있기 때문에
알파벳순으로 정렬 후에 백트랙킹으로 경로를 찾습니다.

import java.util.*;

class Solution {
    
    String[][] sortedTickets;
    boolean[] used;
    String[] answer;
    int n;
    
    
    public String[] solution(String[][] tickets) {
        //만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
        //알파벳순 정렬 -> 알파벳순으로 가능여부를 확인
        Arrays.sort(tickets, (t1, t2) -> {
            if(t1[0].equals(t2[0])) {
                return t1[1].compareTo(t2[1]);
            }
            return t1[0].compareTo(t2[1]);
        });
        sortedTickets = tickets;
        n = tickets.length;
        used = new boolean[n];
        
        String[] path = new String[n+1];
        String start = "ICN";
        path[0] = start;
        dfs(start, 0, path);
        
        return answer;
    }
    
    public boolean dfs(String curr, int depth, String[] path) {
        if(depth == n) {
            answer = path;
            return true;
        }
        
        for(int i=0; i<n; i++) {
            if(used[i] || !curr.equals(sortedTickets[i][0])) continue;
               
            used[i] = true;
            path[depth+1] = sortedTickets[i][1];
            
            if(dfs(sortedTickets[i][1], depth+1, path)) {
                return true;
            }
            
            used[i] = false;
        }
        
        return false;
    }
}