[PGS] 여행경로 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.*;

class Solution {
    
    static ArrayList<String> results;
    static boolean[] used;
    
    public String[] solution(String[][] tickets) {
        int n = tickets.length;
        results = new ArrayList<>();
        used = new boolean[n];
        
        dfs(0, n, "ICN", "ICN", tickets);
        Collections.sort(results);
        
        return results.get(0).split(" ");
    }
    
    private void dfs(int depth, int n, String now, String result, String[][] tickets) {
        if (depth == n) {
            results.add(result);
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            String from = tickets[i][0];
            String to = tickets[i][1];
            
            if (now.equals(from)) {
                used[i] = true;
                dfs(depth+1, n, to, result + " " + to, tickets);
                used[i] = false;
            }
        }
    }
}

📄 해설

접근

• DFS를 사용해서 푸는 문제이다.
• 모든 항공권을 사용하고, 여러가지 경로가 존재할 수 있다는 점에서 DFS 라고 접근해야함
• 풀이에 대한 접근은 단순하게 접근했다. 재귀함수 내에서, 현재 공항이 출발지인 모든 항공권에 대해 DFS를 수행하는 것으로 접근했다.
• 모든 항공권을 사용했다면 경로 리스트에 경로를 추가하고, 모든 탐색이 끝나면 경로 리스트를 정렬해서 알파벳 순으로 빠른 경로를 정답으로 낸다.

과정

• 사용하는 추가 변수는 경로들을 담을 경로 리스트 results 와 방문여부를 체크할 used 배열이다.
• results 와 used 를 초기화하고 DFS를 바로 수행한다.
  • 첫 시작점은 무조건 "ICN" 이 되어야하므로, 현재 공항을 나타내는 변수 now와 현재 경로 result는 모두 "ICN" 으로 시작한다.
  • 모든 항공권을 사용한 것은 depth == n 으로 판단하고, 이때 results 에 result 를 추가한다.
  • tickets 를 순회하면서, 사용하지 않은 항공권에 대해 now 와 출발지점start(tickets[i][0]) 이 같은지를 비교한다.
  • 같다면 방문처리를 하고 도착지점 to(tickets[i][1]) 을 now 자리에 넣고, result 에 추가한 뒤 재귀호출한다.
  • 해당 재귀가 끝나면 다른 경우도 탐색해야하므로 방문처리를 풀어준다.
• DFS가 완전히 종료되고 나면 Collections.sort() 를 통해 알파벳 순으로 경로를 정렬해준다.
• 이때 오름차순으로 정렬되므로 0번 경로가 정답이 되며, 배열로 반환하기 위해 String.split(" ") 을 통해 공백 기준으로 분리해서 반환해주면 된다.