[pro] 프로그래머스 level3 43164 여행경로 (Java) - DFS

[문제]

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

프로그래머스

 

[풀이]

DFS 문제. 여러 경로가 나오면 사전순으로 정렬 후 첫번째 경로를 반환한다.

 

[코드]

 

import java.util.*;

class Solution {
    List<String> list = new ArrayList<>();
    boolean[] used;
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        //방문하는 공항 경로를 배열에 담아 return 
        
        used = new boolean[tickets.length];
        
        dfs(0, "ICN", "ICN", tickets);
        
        Collections.sort(list);
        
        return list.get(0).split(" ");
    }
    
    public void dfs(int depth, String now, String route, String[][] tickets){
        if(depth==tickets.length){
            list.add(route);
            return;
        }
        
        for(int i=0; i<tickets.length; i++){
            if(now.equals(tickets[i][0]) && !used[i]){
                used[i] = true;
                dfs(depth+1, tickets[i][1], route+" "+tickets[i][1], tickets);
                used[i] = false;
            }
        }
    }
}