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

• 문제 - 프로그래머스 "여행경로"

풀이 과정

1. 주어진 공항의 이름을 오름차순 정렬한다. 이동 가능한 경로가 2개 이상일 경우 알파벳의 오름차순으로 경로를 결정하기 위해 사용한다.
2. 이름의 오름차순 정렬한 공항들에 index를 설정한다. 이 [이름 - index] 관계는 주어진 티켓에 따른 각 공항별 잔여 방문 횟수를 나타내는 2차원 배열을 나타내기 위해 사용한다.
3. 위 1과 2에서 준비한 결과물을 바탕으로 출발/도착 공항별 잔여 방문 횟수를 2차원 배열로 나타낸다. 문제에서 주어진 예제 1번의 경우 아래의 표와 같이 나타낼 수 있다.
   

   

4. DFS 방식으로 방문할 공항을 탐색한다.
5. 최종 결과물을 주어진 조건에 맞게 공항의 이름으로 변경하여 반환한다.

DFS 전개

1. 주어진 출발공항을 현재까지 확인한 여행경로 Queue에 추가한다. 이후 해당 출발공항에 대해서 도착공항을 나타내는 1차원 배열에 대해 다음 과정을 진행한다.
   • 예를 들어, 주어진 예제 1번에서 ICN 공항에서 출발할 때를 가정하면, 여행경로 Queue는 { 2 (=ICN) } 이고 도착공항 배열은 { HDN(0) = 0, IAD(1) = 0, ICN(2) = 0, JFK(3) = 1} 이다.
2. 배열을 순회하며 잔여 방문 횟수(배열의 원소값)이 0이 아닌 곳을 찾는다. 위 예제에서는 JFK 공항이 해당된다.
3. 다음 과정을 진행한 후 2에서 찾은 도착 공항을 새로운 출발 공항으로 삼아 다시 1번 과정부터 수행한다.
   • 도착공항 배열에서 이번 도착공항의 원소값을 -1 해 준다.
     • 예제 1번에 대해서 다음과 같이 ICN 을 출발공항으로 하는 도착공항 배열이 변경된다. -> { HDN(0) = 0, IAD(1) = 0, ICN(2) = 0, JFK(3) = 1 - 1 = 0}
   • 한 번 이동한 것이므로 남은 티켓의 갯수를 -1 해 준다.
4. DFS를 빠져나왔을 때 남은 티켓의 갯수가 0이 아니라면 주어진 조건을 모두 만족하는 여행경로가 아니므로 (주어진 모든 티켓을 사용하지 않았음에도 더이상 현재 공항에서 사용 가능한 티켓이 없으므로) 티켓을 사용하기 전으로 되돌린다.
   • 남은 티켓의 갯수 +1
   • 사용한 티켓의 도착공항에 대한 잔여 방문 횟수 +1
   • 현재까지의 여행 경로에서 사용한 티켓의 도착공항 제거

Code

import java.util.*;

class Solution {
    public static int ticketsLeft;

    public String[] solution(String[][] tickets) {
        ticketsLeft = tickets.length;

        // 1. 공항들의 이름을 오름차순 정렬
        // 오름차순 정렬 ->
        // 가능한 경로가 복수일 경우 알파벳의 오름차순으로 경로를 return
        Set<String> airportNames = new HashSet<>();
        for (String[] ticket : tickets) {
            airportNames.add(ticket[0]);
            airportNames.add(ticket[1]);
        }

        String[] airports = airportNames.stream().sorted().toArray(String[]::new);

        // 2. 계산 편의성을 위한 [공항 이름 - 인덱스] 관계 설정
        Map<String, Integer> nameToIdx = new HashMap<>();
        Map<Integer, String> idxToName = new HashMap<>();
        for (int i = 0; i < airports.length; i++) {
            nameToIdx.put(airports[i], i);
            idxToName.put(i, airports[i]);
        }

        // 3. [출발지 - 도착지] 관계에 대해서, 각 공항에 대한 잔여 방문 횟수 grid 생성
        int[][] grid = new int[airports.length][airports.length]; // [from][to]
        for (String[] ticket : tickets) {
            int fromIdx = nameToIdx.get(ticket[0]);
            int toIdx = nameToIdx.get(ticket[1]);
            grid[fromIdx][toIdx]++;
        }

        // 4. 여행 루트 탐색 준비
        ArrayDeque<Integer> myRoute = new ArrayDeque<>();
        String startingPoint = "ICN";
        int startingIdx = nameToIdx.get(startingPoint);
        myRoute.offer(startingIdx);

        // 5. DFS 방식으로 전체 루트를 탐색
        dfs(startingIdx, grid, myRoute);

        // 6. index 값으로 주어진 결과를 String으로 변환
        return myRoute.stream().map(idxToName::get).toArray(String[]::new);
    }

    private void dfs(int currentIdx, int[][] grid, ArrayDeque<Integer> myRoute) {
        int[] currentlyAvailableDestinations = grid[currentIdx];

        for (int i = 0; i < currentlyAvailableDestinations.length; i++) {
            if (currentlyAvailableDestinations[i] != 0) {
                // i = 다음 도착지의 index
                myRoute.offer(i);
                currentlyAvailableDestinations[i]--;
                ticketsLeft--;

                dfs(i, grid, myRoute);

                if (ticketsLeft != 0) {
                    // 목적지에 도착하였으나 티켓이 남았을 경우, 마지막으로 사용했던 티켓을 취소하고 다른 티켓을 먼저 사용하도록 설정
                    currentlyAvailableDestinations[i]++;
                    ticketsLeft++;
                    myRoute.pollLast();
                }
            }
        }
    }
}

결과