Lv.3 여행경로

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

프로그래머스

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;

class Solution {
    public String[] solution(String[][] tickets) {
        HashMap<String, ArrayList<String>> map = new HashMap<>(); // 출발지(key): 목적지 목록(value)의 형태로 저장
        
        for (String[] ticket : tickets) {
            map.putIfAbsent(ticket[0], new ArrayList<>()); // 해당 출발지가 처음 등장한다면 빈 ArrayList를 값으로 가지도록 한다.
            ArrayList<String> dests = map.get(ticket[0]); // 목적지 목록(value)에
            dests.add(ticket[1]); // 목적지를 추가한다.
        }
        for (Entry<String, ArrayList<String>> entry : map.entrySet()) { // 맵의 요소들을 불러와서
            ArrayList<String> dests = entry.getValue(); // 각각의 목적지 목록을
            dests.sort(null); // 오름차순으로 정렬한다.
        }

        String[] routes = new String[tickets.length + 1]; // 경로를 저장한다.
        
        return dfs(map, routes, "ICN", 0); // 경로 return
    }
    
    static String[] dfs(HashMap<String, ArrayList<String>> map, String[] routes, String now, int idx) {
        routes[idx] = now; // 지금 방문한 장소를 경로에 추가

        if (idx + 1 == routes.length) { // 모든 티켓을 사용하여 모든 장소를 방문했다면
            return routes; // 경로 return
        }

        ArrayList<String> dests = map.get(now); // 지금 방문한 장소로부터 갈 수 있는 목적지 목록이다.
        
        if (dests == null) { // 값이 null인 경우는 최종 목적지어야 하는 장소에 더 빨리 방문한 경우이므로
            return null; // null을 return하고 다른 경로를 탐색한다.
        }
        for (int i = 0; i < dests.size(); i++) {
            String dest = dests.get(i); // 목적지 하나씩 조회
            if (dest == null) { // 이미 방문한 장소라면
                continue; // 다음 목적지를 확인한다.
            }
            String tmp = dest; // 임시로 저장한다.
            dests.set(i, null); // 목적지 대신 null을 저장하여 방문처리한다.
            String[] result = dfs(map, routes, dest, idx + 1); // 목적지 방문
            dests.set(i, tmp); // 방문처리를 해제하여 모든 순열을 확인할 수 있도록 한다.
            if (result != null) { // 모든 장소를 방문한 경우
                return result; // 경로를 return하고
            } // 아니라면 다른 순열을 확인한다.
        }
        
        return null; // 모든 장소를 방문할 수 없는 경로였다면 null을 return하고 다른 경로를 탐색한다.
    }
}