프로그래머스 - 여행경로[Java]

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

프로그래머스

 

처음 작성한 코드는 테스트케이스 1번 2번에서 실패했다.

 

 

그 이유는 위 케이스에서 ICN에서 출발하여 알파벳순으로 더 먼저오는 AAA로 가는 경로만 구했기 때문에 모든 경로를 탐사하는 루트를 구하지 못했다.

 

따라서 모든 경로를 구하기 위해서 백트래킹을 해야된다는 것을 알게 되었다.

 

<정답코드>

import java.util.*;

class Solution {
    public static  boolean[] visit;
    public static List<String> result = new LinkedList<>();
    
    public String[] solution(String[][] tickets) {
        String[] answer =new String[tickets.length+1];
        visit = new boolean[tickets.length];
  
        Arrays.sort(tickets, Comparator.comparing(o -> o[1])); //도착지 알파벳순으로 정렬

        
        dfs(tickets,"ICN",0,new ArrayList<>());

        
        return result.toArray(new String[0]);
    }
    public void dfs(String[][] tickets,String current,int count,List<String> path){
     
        path.add(current);
        
        if(count==tickets.length){
            if(result.isEmpty() || path.toString().compareTo(result.toString())<0){
                result.clear();
                result.addAll(path);
            }
            return;
        }
        
        for(int i=0; i<tickets.length; i++){
            if(tickets[i][0].equals(current) && visit[i]==false){
                visit[i]=true;
                dfs(tickets,tickets[i][1],count+1,new ArrayList<>(path));
                visit[i]=false; //다시 방문 전 상태로 만들어 모든 경로 탐색 가능
            }
        }
        return;
    }
}