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

문제 링크

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

풀이 과정

항공권 정보(시작 공항 → 도착 공항)들이 주어지고, 항상 인천 공항(ICN) 에서 시작해 모든 항공권을 다 사용하는 경로를 리턴하는 문제입니다.

가능한 경로가 여러 개일 경우, 알파벳 순서가 가장 앞서는 경로를 리턴해야 하므로 이에 중첩 ArrayList를 사용했습니다. path에는 dfs를 돌며 매번 들르는 공항의 이름을 담아 두었고, 모든 항공권을 다 사용하면 path에 담긴 공항 이름들을 모두 tmp 에 옮겨 담았고, 이를 최종 경로를 보관하는 list에 추가했습니다.

마지막으로, Collections의 sort를 통해 알파벳이 가장 앞서는 경로를 0번 인덱스에 오게끔 정렬하였고, 0번 인덱스에 담긴 경로 정보를 리턴합니다.

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Main {
    static ArrayList<ArrayList<String>> list;

    public static ArrayList<String> solution(String[][] tickets) {
        boolean[] used = new boolean[tickets.length];
        list = new ArrayList<>();
        ArrayList<String> path = new ArrayList<>();

        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN") && !used[i]) {
                path.clear();

                path.add("ICN");
                path.add(tickets[i][1]);

                dfs(i, tickets, used, 1, path);
            }
        }

        Collections.sort(list, new Comparator<ArrayList<String>>() {
            @Override
            public int compare(ArrayList<String> o1, ArrayList<String> o2) {
                int idx = 0;
                while (idx < o1.size() - 1 && o1.get(idx).equals(o2.get(idx)))
                    idx++;

                return o1.get(idx).compareTo(o2.get(idx));
            }
        });

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).get(0).equals("ICN"))

                return list.get(i);
        }
        return list.get(0);
    }

    public static void dfs(int idx, String[][] tickets, boolean[] used, int cnt, ArrayList<String> path) {
        used[idx] = true;

        if (cnt == tickets.length) {
            ArrayList<String> tmp = new ArrayList<>();
            for (String s : path) {
                tmp.add(s);
            }

            list.add(tmp);
            used[idx] = false;

            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (tickets[idx][1].equals(tickets[i][0]) && !used[i]) {
                path.add(tickets[i][1]);
                dfs(i, tickets, used, cnt + 1, path);
                path.remove(path.size() - 1);
            }
        }

        used[idx] = false;
    }

    public static void main(String[] args) {
//        String[][] tickets = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}};
//        String[][] tickets = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL", "SFO"}};
//        String[][] tickets = {{"ICN", "A"}, {"A", "C"}, {"A", "D"}, {"D", "B"}, {"B", "A"}};
//        String[][] tickets = {{"ICN", "A"}, {"ICN", "A"}, {"A", "ICN"}};
//        String[][] tickets = {{"ICN", "A"}, {"A", "B"}, {"B", "A"}, {"A", "ICN"},{"ICN", "A"}};
//        String[][] tickets = {{"ICN", "A"}, {"ICN", "A"}, {"ICN", "A"}, {"A", "ICN"},{"A", "ICN"}};
//        String[][] tickets = {{"ICN", "A"}, {"ICN", "B"}, {"B", "ICN"}};
        String[][] tickets = {{"ICN", "BOO"}, {"ICN", "COO"}, {"COO", "DOO"}, {"DOO", "COO"}, {"BOO", "DOO"}, {"DOO", "BOO"},
                {"BOO", "ICN"}, {"COO", "BOO"}};

        solution(tickets);
    }
}