[프로그래머스, 43164] 여행경로 (java)

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

프로그래머스

728x90

---

메모리: 68.2 MB, 시간: 0.87 ms

사용 알고리즘: DFS

 

동일한 공항을 출발지로 하는 티켓이 여러 개일 수 있다.

따라서 공항을 key값으로,

key 공항을 출발지로 하는 티켓의 인덱스를 담은 리스트를 value값으로 가지는 Map을 만들어준다.

 

위의 Map을 만들기 전에,

가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 해야 하므로,

도착지를 기준으로 tickets을 사전순 정렬해 준 뒤, 정렬을 끝낸 tickets의 인덱스로 Map을 만든다.

 

DFS로 가능한 경로를 따라 이동 중,

아직 티켓을 다 사용하지 못했는데 더 이상 이동할 수 있는 공항이 없다면

다시 뒤로 돌아가 경로를 바꿔준다.

import java.util.*;

class Solution {
    
    static String[][] tickets;
    static Map<String, ArrayList<Integer>> info;
    static boolean[] visited;
    static String[] answer;
    
    public String[] solution(String[][] tickets) {
        
        this.tickets = tickets;
        
        // 도착지를 기준으로 사전순 정렬
        Arrays.sort(tickets, (o1, o2) -> o1[1].compareTo(o2[1]));
        
        // 공항별 출발지로 가지고 있는 티켓 정보
        info = new HashMap<>();
        ArrayList<Integer> list;
        for(int i = 0; i < tickets.length; i++) {
            
            list = info.get(tickets[i][0]);
            
            if(list == null) {
                list = new ArrayList<>();
                info.put(tickets[i][0], list);
            }
            
            list.add(i);
        }
        
        // dfs로 가능한 경로 구하기
        visited = new boolean[tickets.length];
        
        answer = new String[tickets.length + 1];
        answer[0] = "ICN";
        
        dfs(0);
        
        return answer;
    }
    
    // idx := 몇 번째 여행지인지
    private static boolean dfs(int idx) {
        
        if(idx == tickets.length) {
            return true;
        }
        
        // 현재 위치에서 갈 수 있는 다음 목적지
        ArrayList<Integer> list = info.get(answer[idx]);
        
        // 다음으로 갈 수 있는 경로가 없음
        if(list == null) return false;
        
        // 다음으로 갈 수 있는 경로가 있음
        int next;
        for(int i = 0; i < list.size(); i++) {
            next = list.get(i);
            if(!visited[next]) {
                visited[next] = true;
                answer[idx + 1] = tickets[next][1];
                // 현재 경로가 가능한 경로인 경우
                if(dfs(idx + 1)) return true;
                visited[next] = false;
            }
        }
        
        // 현재 경로가 잘못된 경우
        return false;
    }
}