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

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
	
	// 여행경로
	// 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
	// 주어진 공항 수는 3개 이상 10,000개 이하입니다.
	// 주어진 항공권은 모두 사용해야 합니다.
	// 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
	// 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
	
	static boolean[] visited;
	static ArrayList<String> travelRouteList;
	
	public static void dfs(String start, String route, String[][] tickets, int cnt) {
		if (cnt == tickets.length) {
			travelRouteList.add(route);
			return;
		}
		
		for (int i = 0; i < tickets.length; i++) {
			
			if (start.equals(tickets[i][0]) && !visited[i]) {
				visited[i] = true;
				dfs(tickets[i][1], route + " " + tickets[i][1], tickets, cnt + 1);
				visited[i] = false;
			}
		}
	}
	
	public static String[] solution(String[][] tickets) {
		String[] answer = {};
		int cnt = 0;
		visited = new boolean[tickets.length];
		travelRouteList = new ArrayList<>();
		
		dfs("ICN", "ICN", tickets, cnt);
		
		Collections.sort(travelRouteList);
		answer = travelRouteList.get(0).split(" ");
		
		for (String strRoute : answer) {
			System.out.print(strRoute + " ");
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[][] tickets = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}}; // {"ICN", "JFK", "HND", "IAD"}
//		String[][] tickets = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}}; // {"ICN", "ATL", "ICN", "SFO", "ATL", "SFO"}
		
		System.out.println(solution(tickets));
	}
}

프로그래머스 여행경로 문제 풀이 Java