** 여행경로 **

 

 

import java.io.*;
import java.util.*;

class Solution {
    static ArrayList<String> al = new ArrayList<>(); //경로 저장
    static boolean[] visited ;
        
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(0, "ICN", "ICN", tickets);
        
        //알파벳 순 정렬해서 맨 앞 경로 뺴내기
        Collections.sort(al);
        
        
        return al.get(0).split("->");
    }
    
    //cnt: 사용한 티켓 개수
    //now: 현재 있는 도시 ([?,0]이 now인 곳에서 찾아야 함)
    //path: 경로 저장(답이 될 수 있는)
    public static void dfs(int cnt, String now, String path, String[][] tickets) {
        //종료 조건( 다 돌았으면 경로 저장 )
        if(cnt == tickets.length) {
            al.add(path);
            return;
        }
        
        //dfs 수행
        //now가 [?,0]과 같고 + 아직 미방문
        for(int i=0; i<tickets.length; i++) {
            if(!visited[i] && now.equals(tickets[i][0])) {
                visited[i] = true;
                dfs(cnt+1, tickets[i][1], path+"->"+tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
}

 

 

패악질:

1. tickets배열을 sort를 해버리고 시작하려 했따. 

  음 근데 했어도 됐었을 거 같은데??????

  음 아니다