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

https://school.programmers.co.kr/learn/courses/30/lessons/43164

코드

import java.util.*;

class Solution {
    static boolean[] used;
    static List<String> result = new ArrayList<>();

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

        // 탐색 수행
        dfs(tickets, "ICN", "ICN", 0);

        // 사전 순으로 리스트 정렬
        Collections.sort(result);

        // 문자열 리스트 데이터를 사전 순으로 정렬했으므로 첫 번째 요소가 정답
        return result.get(0).split(" ");
    }

    static private void dfs(String[][] tickets, String departure, String route, int depth) {
        if (depth == tickets.length) {
            result.add(route);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            // 아직 사용하지 않고 출발지가 동일한 티켓
            if (!used[i] && tickets[i][0].equals(departure)) {
                used[i] = true;
                dfs(tickets, tickets[i][1], route + " " + tickets[i][1], depth + 1);
                used[i] = false;
            }
        }
    }
}

풀이

DFS와 백트래킹을 사용했다. 출발지가 departure인 티켓을 찾고서 다음 경로를 탐색한다. 하나의 경로가 완성되면 재귀 스택이 종료되며 방문 여부(visited)를 해제한다. (백트래킹)

입력에 따라, 완성된 경로는 2개 이상일 수 있다. 문제에서는 알파벳 순으로 더 빠른 경로를 원하므로 정렬된 경로들 중 첫 번째 경로가 정답이다.