Programmers 여행 경로 java 풀이

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

나의 풀이

 DFS 방식으로 문제풀이 접근, 모든 티켓을 소모했을 경우에 리턴하도록 했다. 문제는 전체 티켓을 사용하는 코스가 여러개 발생할 경우(예제2) 알파벳 순서대로 빠른 공항을 먼저 가도록 이기 때문에 배열을 정렬하고 DFS를 시작하기로 했다. 문제 자체는 이전 DFS문제풀이와 사실상 다를게 없기 때문에 금방 코드를 작성했다. 아쉬운 점은 tickets배열을 정렬하는데 있어서 배열이 길어지면 정렬비용이 상당할텐데 이 점을 다른 풀이로 접근해보고 싶었다. 여러 머리를 써봤는데 DFS 방식으로 탐색을 마치고 이전 경로와 비교해서 값이 작은 경로를 선택하도록 하는 방식으로 코드를 짜려니 오히려 복잡해졌다.. 결국 처음 작성한 코드로 풀이를 끝냈다. 

 

 

코드

import java.util.*;

class Solution {
    static int N;
    static boolean[] visited;
    public String[] solution(String[][] tickets) {
        N = tickets.length;
        visited = new boolean[tickets.length];
        String[] answer = new String[N+1];
        
        Arrays.sort(tickets, new Comparator<String[]>(){
            public int compare(String[] arr1, String[] arr2) {
                if(arr1[0].compareTo(arr2[0])!=0) {
                    return arr1[0].compareTo(arr2[0]);
                }
                return arr1[1].compareTo(arr2[1]);
            }
            
        });
        
        answer[0] = "ICN";
        dfs(0, tickets, answer);
        
        return answer;
    }
    
    public static boolean dfs(int depth, String[][] tickets, String[] answer) {
        if(depth==N) {
            return true;
        }
        
        for(int i=0; i<tickets.length; i++) {
            if(visited[i] || !answer[depth].equals(tickets[i][0]))
                continue;
            
            visited[i] = true;
            answer[depth+1] = tickets[i][1];
            if(dfs(depth+1,tickets, answer))
                return true;
            visited[i] = false;
        }
        
        return false;
    }
}