Sangil's blog

어떤문제

해당 문제는 항공권 정보가 담긴 2차원 배열 TICKETS가 주어지고, 항공권을 사용해서 공항을 경유하는 경로를 찾는 문제이다. 이때 모든 항공권을 다 사용해야 하고, 알파벳 순서가 앞서는 경로를 찾아야 한다.

어떻게

아래와 같이 티켓 {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}}이 주어 졌을 때, ICN 을 시작으로 전체 항공권을 사용 할 수 있는 경우를 LEVEL6까지 탐색하면 항공권을 전체 다 사용 할 수 있는 경우를 구할 수 있다. 해당 문제를 보고 이 그림을 떠올리는게 문제를 푸는 핵심이였던거 같다.

사진을 보면 모든 항공권을 사용 할 수 있는 경우는 3가지 경우가 있다는 것을 알 수 있다. 
1. ICN->SFO->ATL->ICN->ATL->SFO
2. ICN->ATL->ICN->SFO->ATL->SFO
3. ICN->ATL->SFO->ATL->ICN->SFO

이때, 경로가 같을 경우 알파벳 순으로 지정한다고 했으니 답은 2번이 된다. 트리를 생각하는거에 + 정렬순서를 둠으로 문제가 더욱 까다러웠던거 같다. 정렬을 생각하며 다른길로 샐수도... 저와같이..ㅎ

코드(https://github.com/ChoiSangIl/algorithm/tree/master/BFS%2CDFS/programmers_C30_L43164_%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C)

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

class A211015 {
    static ArrayList<String> result = new ArrayList<String>();
    
    public static void main(String[] args) {
    	String[][] tickets = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}};
    	A211015 s = new A211015();
    	System.out.println(Arrays.toString(s.solution(tickets)));
    }
    
    public String[] solution(String[][] tickets) {
        //방문경로를 저장하기위한 배열
        Boolean[] visited = new Boolean[tickets.length];
	Arrays.fill(visited, Boolean.FALSE);
        //깊이탐색 시작
	dfs(visited, "ICN", "", tickets, 0);
        //알파벳순서로 가장 빠른 경로를 가져오기 위한 정렬
        Collections.sort(result);
        
        String[] answer = result.get(0).split(",");
        return answer;
    }
    
    static void dfs(Boolean[] visited, String station, String path, String[][] tickets, int index)  {
		if("".equals(path)) {
			path = station;
		}else {
			path = path + ","+ station;
		}		
		
		if(index == tickets.length) {
			result.add(path);
		}
		
		for(int i=0; i<tickets.length; i++) {
                        //사용하지 않은 티켓이고 가는 경로가 있을 경우
			if(!visited[i] && tickets[i][0].equals(station)) {
				visited[i] = true;
				dfs(visited, tickets[i][1], path, tickets, index+1);
				visited[i] = false;
			}
		}
	}
}