[프로그래머스] 여행경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

• 이동 가능한 모든 경로 중 알파벳 순서가 앞서는 경로를 return하면 된다. 그리고 모든 항공권을 사용해야 한다. 따라서 dfs를 사용했다.
• 그리고 dfs 중간에 usedTicket[i] = false로 초기화해줘야 한다. 예를 들어 JFK를 먼저 방문했으면 그 다음 경로에서는 JFK를 방문하지 못하도록 방문처리를 해줬지만, 다른 공항을 먼저 방문한 후의 경로에서는 JFK를 방문할 수 있어야 하기 때문이다. 
  

import java.util.*;

class Solution {

    String[][] tickets;
    List<String> answerList = new ArrayList<>();
    boolean[] usedTicket;

    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        usedTicket = new boolean[tickets.length];

        // ICN에서 출발
        dfs("ICN", "ICN", 0);
        Collections.sort(answerList);
        return answerList.get(0).split(" ");
    }

    private void dfs(String start, String route, int cnt) {
        if (cnt == tickets.length) {
            answerList.add(route);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals(start) && !usedTicket[i]) {
                usedTicket[i] = true;
                dfs(tickets[i][1], route + " " + tickets[i][1], cnt + 1);
                usedTicket[i] = false;
            }
        }
    }
}