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

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

프로그래머스

 

⭐️ 중요 포인트

1. graph에 출발지와 도착지에 대한 정보를 기록한다. 이 때, isNotUsed와 graph를 따로 정의한 이유는 조건 중 "만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다."라는 조건을 맞추기 위해서 graph의 도착지는 List 형식으로 저장하였다. 다만 그래프를 순회하면서 중복 순회를 방지하기 위해서 값을 저장해야 한다. 이 때, List.contains() 를 사용하게 되면 한 번 탐색을 할 때마다 O(N)의 시간복잡도가 소요되는데, HashMap.getOrDefault()를 사용하면 일반적으로 O(1)의 시간복잡도가 소요된다. 따라서 그래프에 대한 저장은 List를 사용하고, 해당 노드를 방문했는지에 대한 여부는 HashMap을 사용했다.

2. dfs에 진입하면 answerList에 해당 from 값을 추가. dfs를 탈출할 때는 answerList에서 해당 값을 삭제해야한다. 그래야 현재까지의 이동경로를 추적할 수 있다.

3. usedTicketCount를 dfs 돌 때마다 따로 관리하여 해당 값이 기존에 입력받은 tickets의 값과 같아지면 모든 티켓을 사용했다는 것이므로 dfs를 종료한다. (어떻게 티켓값만 가지고 판단할 수 있냐? -> for 문 아래서 애초에 티켓이 없는 공항에 대한 여행은 하지 않기 때문에 무조건 티켓이 있는 도착지로만 이동할 수 있다. 따라서 모든 티켓이 소진되었다는 것은 모든 여행지를 돌아다녔다는 뜻이 된다.)

 

import java.util.*;

class Solution {
    
    static String[][] tickets;
    
    static Map<String, ArrayList<String>> graph;
    static List<String> answerList;
    static String[] answer;
    // Map<from, Map<to, count>>
    static Map<String, Map<String, Integer>> isNotUsed;
    static boolean endFlag;
    
    void init(String[][] tickets) {
        
        this.tickets = tickets;
        
        graph = new HashMap<>();
        answerList = new ArrayList<>();
        isNotUsed = new HashMap<>();
        endFlag = false;
    }
    
    void solve() {
        // 연결
        for (int i = 0; i < tickets.length; i++) {
            String from = tickets[i][0];
            String to = tickets[i][1];
            addTicket(from, to);
        }
        
        // 각 노드에 대해서 사전순 정렬
        for (List list: graph.values()) {
            Collections.sort(list);
        }
        
        // 시작은 인천공항부터
        dfs("ICN", 0);
    }
    
    void dfs(String from, int usedTicketCount) {
        if (endFlag) {
            return;
        }
        
        // 현재 공항을 answer에 저장
        answerList.add(from);
        
        if (tickets.length == usedTicketCount) {
            endFlag = true;
            answer = answerList.toArray(new String[0]);
            return;
        }
        
        
        List<String> directions = graph.getOrDefault(from, new ArrayList<String>());
        
        for (int i = 0; i < directions.size(); i++) {
            String to = directions.get(i);
            
            // 아직 사용하지 않은 티켓이 있으면 출발
            Map<String, Integer> ticket = isNotUsed.get(from);
            if (ticket.getOrDefault(to, 0) > 0) {
                // 티켓 소모 후 재귀
                ticket.put(to, ticket.get(to) - 1);
                dfs(to, usedTicketCount + 1);
                // 해당 티켓에 대한 테스트가 끝났으면 다시 티켓 복구
                ticket.put(to, ticket.get(to) + 1);
            }
        }
    
        // 현재 공항에서 모든 경우의 수를 따졌으면 remove
        answerList.remove(answerList.size() - 1);
    }
    
    // 단방향 그래프 연결
    void addTicket(String from, String to) {
        graph.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        // (from, to)에 따른 티켓 생성 (이 때, from과 to가 같은 티켓이 있을 수 있으므로 from과 to가 같은 경우에는 ticket의 개수를 count한다.)
        isNotUsed.computeIfAbsent(from, k -> new HashMap<>()).put(to, isNotUsed.get(from).getOrDefault(to, 0) + 1);
    }
    
    public String[] solution(String[][] tickets) {
        init(tickets);
        solve();
        
        return answer;
    }
}