[JAVA/DFS] 여행경로

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

프로그래머스

 

 

 

import java.util.*;

class Solution {

    private String SPACE = " ";
    List<String> travelList = new ArrayList<>();
    boolean[] ticketUsed;
    int ticketCnt;
    
    public String[] solution(String[][] tickets) {
        
        ticketCnt = tickets.length;
        ticketUsed = new boolean[ticketCnt];
        
        dfs("ICN", "ICN", tickets, 1);
        
        Collections.sort(travelList);
        
        return travelList.get(0).split(SPACE);
    }
    
    public void dfs(String departure, String tmp, String[][] tickets, int cnt) {
        if(cnt > ticketCnt) {
            // 모든 경로 탐색 완료
            travelList.add(tmp);
            return;
        }
        
        for(int i=0; i<tickets.length; i++) {
            if(!ticketUsed[i] && tickets[i][0].equals(departure)) {
                // 해당 티켓 사용여부 임시저장
                ticketUsed[i] = true;
                dfs(tickets[i][1], tmp + SPACE + tickets[i][1], tickets, cnt+1);
                // 다시 사용하지 않음으로 돌리기
                ticketUsed[i] = false;
            } 
        }
    }
}