여행경로

import java.util.*;
class Solution {
    private static ArrayList<String> travelCourse;
    private static boolean flag = true;
 
    public static void SetTravelCourse(HashMap<String, ArrayList<String>> allPath, ArrayList<String> tmpCourse,
            String destination, int i, int n) {
        // 처음으로 성공한 코스를 저장하고 종료
        if (i == n && flag) {
            travelCourse = new ArrayList<String>(tmpCourse);
            flag = false;
            return;
        }
 
        String source = destination;
        // 경로가 없는 경우
        if (!allPath.containsKey(source))
            return;
        
        ArrayList<String> path = allPath.get(source);
        // 모든 코스 탐색
        for (int k = 0; k < path.size(); k++) {
            destination = path.remove(k);
            tmpCourse.add(destination);
            SetTravelCourse(allPath, tmpCourse, destination, i + 1, n);
            tmpCourse.remove(tmpCourse.size() - 1);
            path.add(k, destination);
        }
    }
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        HashMap<String, ArrayList<String>> allPath = new HashMap<String, ArrayList<String>>();
 
        // 경로 저장 및 알바벳 순서로 정렬
        for (int i = 0; i < tickets.length; i++) {
            // 경로를 처음 입력할 경우
            if (!allPath.containsKey(tickets[i][0])) {
                ArrayList<String> path = new ArrayList<String>();
                path.add(tickets[i][1]);
                allPath.put(tickets[i][0], path);
            } else { // 이미 경로가 존재할 경우 삽입하고 정렬
                allPath.get(tickets[i][0]).add(tickets[i][1]);
                Collections.sort(allPath.get(tickets[i][0]));
            }
        }
 
        SetTravelCourse(allPath, new ArrayList<String>(Arrays.asList(new String[] { "ICN" })), "ICN", 1,
                tickets.length + 1);
        answer = travelCourse.toArray(new String[0]);
        return answer;
    }
}

HashMap + ArrayList를 이용하여 풀이하였다.

이를 DFS로 탐색하여 첫 번째로 성공하는 코스를 저장하고 바로 종료하도록 하였다.