프로그래머스 : 여행경로

정답은 항상 있다.

 

그러면 str[] 중 str[1] 을 기준으로 정렬해서 0~n을 방문해서 가장먼저 다돌수 있는게 정답이다 ^^

 

 

 

package excirsize;

import java.util.Arrays;
import java.util.Comparator;

public class 여행경로 {
	
	public static void main(String[] args) {
		String[][] tickets = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}};
	
		for(String ans : solution(tickets)) {
			System.out.print(ans +" ");
		}
	}

	static public String[] solution(String[][] tickets) {
		String[] answer = new String[tickets.length+1];
		Arrays.sort(tickets, new CMP());
		boolean[] check = new boolean[tickets.length];

		dfs("ICN", 0, tickets, check, answer);
		return answer;
	}

	static public boolean dfs(String location, int s, String[][] tickets, boolean[] check, String[] answer) {
		answer[s] = location;
		if (s == tickets.length) {
			return true;
		}
		
		for (int i = 0; i < tickets.length; i++) {
			if (check[i])
				continue;

			if (location.equals(tickets[i][0])) {
				check[i] = true;
				
				if (dfs(tickets[i][1], s + 1, tickets, check, answer))
					return true;
				
				check[i] = false;
			}
		}

		return false;
	}

	static public class CMP implements Comparator<String[]> {

		@Override
		public int compare(String[] o1, String[] o2) {
			if(o1[0].equals(o2[0])) {
				return o1[1].compareTo(o2[1]);
			}
			
			return o1[0].compareTo(o2[0]);
		}

	}
}