[프로그래머스][Java] Lv.3 여행경로

---

문제 정리

• 항상 시작점은 "ICN"이어야 한다.
• 공항을 여러 번 방문해도 상관 없지만, 항공권은 한 번 사용하면 다시 사용할 수 없다.
• 모든 티켓을 사용해야 한다.
• 경로가 여러 개라면, 알파벳 순서가 앞서는 경로를 return해야 한다.

 

풀이과정

1. 경로를 알파벳 순으로 만들기 위해, tickets 배열을 알파벳 순서로 정렬합니다.
2. 항상 시작점은 ICN이기 때문에 방문순서 List에 ICN을 넣습니다.
3. DFS를 시작합니다.
4. 이전 티켓의 도착지점은 다음 티켓의 시작지점이 되어야 하므로 start에 값을 넣습니다.
5. tickets을 검사하면서 이전에 사용했던 티켓이 아니고, 티켓의 시작지점이 start와 같은지 확인합니다.
6. 이전 도착지점과 현재 티켓의 출발지점이 같다면,
   해당 티켓을 사용하고 해당 티켓의 도착지점을 방문순서 List에 넣습니다.
7. DFS에 여태까지 사용한 티켓수와 함께 넘겨주고, 4-7번 작업을 반복합니다.
8. DFS 탐색 중, 모든 티켓을 사용했다면 DFS 탐색을 종료합니다.
9. DFS탐색을 완료한 여행 경로를 반환합니다.

---

전체 코드

import java.util.*;
class Solution {
    static boolean[] useTicket;
    static ArrayList<String> visitOrder = new ArrayList<>(); //방문 순서
    static ArrayList<String> answerList = new ArrayList<>(); //정답 여행 경로
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        useTicket=new boolean[tickets.length];
        
        //알파벳 순서로 정렬.
        Arrays.sort(tickets, new Comparator<String[]>(){
            @Override
            public int compare(String[] o1, String[] o2){
                if(o1[0].equals(o2[0]))
                    return o1[1].compareTo(o2[1]);
                else
                    return o1[0].compareTo (o2[0]);
            }
        });
        
        visitOrder.add("ICN"); //처음 시작은 icn
        dfs(tickets,0);
        
        answer = new String[visitOrder.size()];
        for(int i=0;i<answer.length;i++)
            answer[i]=answerList.get(i);
        
        return answer;
    }
    private void dfs(String[][] tickets, int idx){ //idx는 사용한 티켓 수.
        
        //System.out.println(visitOrder);
        //모든 티켓을 사용했으면 종료.
        if(idx==useTicket.length){
            answerList=visitOrder;
            return;
        }
        
        String start=visitOrder.get(visitOrder.size()-1); //이전 도착지
        
        for(int i=0;i<tickets.length;i++){
            if(!useTicket[i] && start.equals(tickets[i][0])){
                useTicket[i]=true;
                visitOrder.add(tickets[i][1]); //도착지 입력
                
                dfs(tickets,idx+1);
                //dfs로 탐색을 마치면 더이상 탐색하지 않음.
                if(answerList.size()>0) break;
                
                visitOrder.remove(visitOrder.size()-1);
                useTicket[i]=false;
            }
        }
    }
}