[Java] 주어진 항공권을 모두 사용한 여행 경로 출력

1. 문제

• 2차원 배열 tickets는 출발지와 도착지가 명시된 항공권 의미
• 출발지는 "ICN"으로 고정
• 모든 도시를 방문할 수 없는 경우는 주어지지 않음
• 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로만 반환

 

2. 해결

DFS 사용

import java.util.*;

class GetRoute {
    boolean[] visited;	// 사용여부 표시
    ArrayList<String> cases;	// 가능한 경로 저장
    
    public String[] getRoute(String[][] tickets) {      
        cases = new ArrayList<String>();
        visited = new boolean[tickets.length];
        int count = 0;    
        
        dfs(tickets, "ICN", "ICN", count);	// dfs 방식으로 경로 탐색
        Collections.sort(cases);	// 가능한 경로들을 알파벳 순서로 정렬
        
        // 문자열로 저장된 경로를 띄어쓰기를 기준으로 나누어 배열에 저장
        String[] answer = cases.get(0).split(" ");	  
        
        return answer;
    }
    
    public void dfs(String[][] tickets, String route, String start, int count) {
        if(count == tickets.length) {	// 모든 항공권을 사용했을 경우 탐색 완료
            cases.add(route);
            return;
        }

        for(int i=0; i<tickets.length; i++) {
        	// 사용하지 않은 항공권의 출발지와 현재 지역 start가 같을 경우
            if(!visited[i] && tickets[i][0].equals(start)) {
                visited[i] = true;	// 사용 표시
                dfs(tickets, route + " " + tickets[i][1], tickets[i][1], count+1);
                visited[i] = false;	// 한개의 경로 탐색 후 다른 경로를 찾기 위해 초기화  
            }             
        }
        
        return;
    }
}