[프로그래머스_Level3] 여행경로

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

프로그래머스

[문제]

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

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

 

[제한사항]

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

 

[코드]

import java.util.*;
class Solution {
    static boolean[] visited;
    static ArrayList<String> route;
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        visited=new boolean[tickets.length];
        route=new ArrayList<>();
        
        dfs("ICN","ICN",0,tickets);
        
        Collections.sort(route); // 알파벳 순으로 경로 정렬
        answer=route.get(0).split(" "); // 알파벳 순서가 앞서는 경로 가져오기
        
        return answer;
    }
    
    // 시작 공항, 여행 경로, 티켓 수, 티켓 배열
    static void dfs(String start, String way, int depth, String[][] tickets){
        if(depth==tickets.length){ // 모든 티켓을 사용한 경우
            route.add(way); // 경로 추가
            return;
        }
        
        for(int i=0;i<tickets.length;i++){
            // 아직 사용하지 않은 티켓이고, 티켓의 출발 공항이 start와 같다면 사용 가능한 티켓
            if(!visited[i]&&start.equals(tickets[i][0])){
                visited[i]=true; // 방문처리
                dfs(tickets[i][1],way+" "+tickets[i][1],depth+1,tickets);
                visited[i]=false;
            }
        }
    }
}

 

[고찰]

 이번 문제는 티켓을 사용하여 나올 수 있는 모든 이동 경로를 구한 후 경로를 알파벳 순으로 정렬하여 가장 첫 번째 값을 가져오면 되는 문제였다. DFS 함수는 시작 공항, 여행 경로, 사용한 티켓 수, 티켓 배열을 들고 다니면서 시작 공항과 사용할 티켓의 출발 공항이 같은지 확인하면서 경로에 추가해주어야 한다.