유형: 그래프 탐색 (DFS, 백트래킹)
문제: 프로그래머스 - 여행경로

문제

유심히 봐야하는 제한 사항 3가지 !!

1. 주어진 항공권을 모두 사용해야 합니다.
2. 가능한 경로가 2개 이상일 경우 알파벳 순서대로 반환합니다.
3. 모든 도시를 방문해야 합니다.

---

실패 코드 (HashMap)

import java.util.*;

class Solution {
    public static ArrayList<String> answerList = new ArrayList<>();
    
    // 항공편 정보와 방문 체크 map 정보 삽입
    public static void addValue(Map<String, List<String>> map, Map<String, Boolean> visited, String key, String value) {
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
        visited.put(key, false);
    }

	// 탐색
    public static void dfs(Map<String, List<String>> map, Map<String, Boolean> visited, String key) {
        answerList.add(key);

        if (map.containsKey(key) && !visited.get(key)) {
            for (int i = 0; i < map.get(key).size(); i++) {
                visited.put(key, true);
                dfs(map, visited, map.get(key).get(i));
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        // 티켓, 방문 체크 저장
        Map<String, List<String>> map = new HashMap<>();
        Map<String, Boolean> visited = new HashMap<>();

        for (int i = 0; i < tickets.length; i++) {
            addValue(map, visited, tickets[i][0], tickets[i][1]);
        }

        
        // 알파벳 기준 정렬
        for (int i = 0; i < map.size(); i++) {
            Collections.sort(map.get(tickets[i][0]), Comparator.naturalOrder());
        }

        // 탐색
        dfs(map, visited,"ICN");

        // 결과
        String[] answer = new String[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }
}

1시간 동안 스스로 코드 짜서 테케 통과하고 신나게 제출했으나 돌아온건 새빨간 실패 결과 😂
갈 수 있는 공항을 알파벳 순으로 정렬 후 탐색을 했는데, 정렬 때문에 갈 수 있지만 제외되어 모든 공항을 갈 수 없었던 것이다.

반례

tickets = [["ICN", "D"], ["D", "ICN"], ["ICN", "B"]]
answer = ['ICN', 'D', 'ICN', 'B']

위 코드를 돌리면

answer = ['ICN', 'B', 'D', 'ICN']

라고 출력된다... 처음부터 정렬하고 탐색을 해서 갈 수 없는 공항이 생겨버린 것이다.

---

백트래킹을 적용한 풀이

모든 공항을 방문할 수 있는 경우의 수를 전부 탐색하고, 정렬을 통해 가장 빠른 공항 경로를 구한다.

1. 처음 출발은 항상 "ICN" 이므로 DFS 호출 시 항상 "ICN"에서 시작하고, 경로를 알기 위해 route 를 같이 전달
2. 종료 조건: DFS에서 모든 티켓을 소진했을 때(경우의 수 전부 탐색했을 때) list에 현재까지의 경로 route를 삽입
3. 모든 경로 탐색을 위해 방문 체크를 해제하고 visited[i] = false 재탐색
4. 모든 경우의 수를 구한 뒤 정렬 Collections.sort()
5. list의 첫번째 문자열을 반환

---

정답 코드

import java.util.*;

class Solution {
    static boolean[] visited;
    static List<String> list = new ArrayList<>();
    
    public String[] solution(String[][] tickets) {
        
        visited = new boolean[tickets.length];
        
        dfs(tickets, "ICN", "ICN", 1);
        Collections.sort(list);
        return list.get(0).split(" ");
        
    }
    
    public static void dfs(String[][] tickets, String start, String route, int depth) {
        if (depth == tickets.length) {
            list.add(route);
            return;
        }

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

reference 👍

쉬운형 [알고리즘] 프로그래머스 - 여행경로 - JAVA
라리 [DFS] 프로그래머스 여행경로 "JAVA"