(코테) 프로그래머스_여행경로 *dfs 백트레킹

 

문제 링크

 

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

 

 

 

import java.util.*;
class Solution {
    //Set<List<String[]>> set = new HashSet<>();
    List<List<String>> set = new ArrayList<>();
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
       List<String> list = new ArrayList<>();        
        boolean[] visted = new boolean[tickets.length];
        list.add("ICN");
        dfs("ICN",list,visted,tickets);                                

            set.sort((a, b) -> {
                for (int i = 0; i < a.size(); i++) {
                    int cmp = a.get(i).compareTo(b.get(i));
                    if (cmp != 0) return cmp;  // ← 여기서 정렬 우선순위가 결정됨
                }
                return 0; // 완전히 같을 때
            });
        return set.get(0).toArray(new String[0]);
                         
    }
    
    public void dfs(String current,List<String> list,boolean[] visted,String[][] tickets ){
        //종료 조건
        if(list.size() ==tickets.length+1){            
            set.add(new ArrayList<>(list));
            return;
        }
        
        for(int i=0;i<tickets.length;i++){        
            if(visted[i]) continue;
            if(!current.equals(tickets[i][0])) continue;            
             

            list.add(tickets[i][1]);
            visted[i]=true;      
            dfs(tickets[i][1],list,visted,tickets);
            
            list.remove(list.size()-1);
            visted[i]=false;            
        }
        
        
    }
}