[프로그래머스 Level3] 여행경로 (JAVA)

[문제]

https://programmers.co.kr/learn/courses/30/lessons/43164?language=java 

코딩테스트 연습 - 여행경로

 

---

[문제 풀기 전]

갈수있는 모든 경로를 탐색하여 알파벳 순서가 앞서는 경로를 반환하면 정답이 되는 문제입니다. 경로가 선택되는 순서에 따라 답이 달라지므로 순열을 사용하여 모든 경우를 만들어 보면 됩니다. 문자열을 다루어야 하는 점에서 어려워 힌트를 봤지만 풀고나니 좋은 문제다 라고 느낀 문제였습니다.

 

---

[문제 풀이]

앞서말했듯이 갈수있는 모든 여행지를 만들어야합니다. 이 여행지를 나중에 알파벳 순서가 앞서는 경로를 반환해야하는데 이를 위해 ArrayList<String> 을 만들어서 경로를 담아 줄 것이고, 해당 티켓을 사용했는지 안했는지 판단하는 Boolean 배열도 필요합니다. DFS 탐색을 통하여 모든 여행지를 만들건데 매개변수 설정이 중요합니다. 제일 중요한 depth 와, 현재 위치, 방문한 여행 경로, 문제에 주어진 tickets배열을 넘겨줄 것입니다.

 

맨 처음 시작은 "ICN" 로 시작하니 현재위치와 방문한 여행경로에 넣어주면서면서 탐색을 시작하게 됩니다. 해당 티켓이 사용이 됐는지, 그리고 현재 위치랑 다음 가야할 곳의 출발지를 비교하여 탐색을 하여 depth가 티켓의 수가 같아지면 해당 여행경로를 ArrayList에 담아줍니다. 탐색이 끝나면 list에는 모든 여행경로가 담겨져 있을 겁니다. 리스트를 정렬을 하면 알파벳 순서가 앞서는 경로가 인덱스 0번째에 위치하게 됩니다. 해당 인덱스의 여행경로를 배열로 담아 리턴을 하면 됩니다.

 

---

[소스 코드]

 

import java.util.*;

class Solution {

    static ArrayList<String> list = new ArrayList<>();
    static boolean useTickets[];

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

        dfs(0, "ICN", "ICN", tickets);

        Collections.sort(list);

        return list.get(0).split(" ");
    }

    static void dfs(int depth, String now, String path, String[][] tickets){
        if (depth == tickets.length) {
            list.add(path);
            return;
        }

        for (int i = 0; i < useTickets.length; i++) {
            if (!useTickets[i] && now.equals(tickets[i][0])) {
                useTickets[i] = true;
                dfs(depth+1, tickets[i][1], path + " " +tickets[i][1], tickets);
                useTickets[i] = false;
            }
        }
    }
}