프로그래머스 - 여행경로(Java)

dfs 문제입니다.

 

주어지는 항공권을 모두 사용해서 여행 경로를 만들어야 합니다.

저의 경우 항공권이 주어지면 해당 정보를 Map에 저장했습니다.

Map에 저장하면 O(1)로 value를 가져올 수 있기 때문에, 반복해서 찾는 것 보다 더 좋다고 생각했습니다.

추가로 항공권 정보를 Map에 저장할 때, 항공권의 위치를 저장했습니다.

중복해서 항공권을 사용하지 않고 여행 경로를 만들기 위함 입니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private static boolean[] visited;
    private static Map<String, List<Node>> map;
    private static List<String[]> ansList;

    private static class Node{
        String city;
        int location; // 항공권 위치를 저장

        public Node(String city, int location) {
            this.city = city;
            this.location = location;
        }
    }

    public static String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        map = new HashMap<>();
        ansList = new ArrayList<>();

        for(int i=0; i< tickets.length; i++){
            String s = tickets[i][0];
            String e = tickets[i][1];

            /*
             * key : 출발지
             * value : [도착지, 항공권 위치]
             * */
            List<Node> list = map.getOrDefault(s, new ArrayList<>());
            list.add(new Node(e, i));
            map.put(s, list);
        }

        // 항공권 정보를 바탕으로 경로를 만듦
        dfs("ICN", "ICN", 0);

        // 경로가 여러개 일 경우 알파벳 순서(오름차순)가 앞서는 경우를 사용함
        ansList.sort((o1, o2) ->{
            for(int i=0; i< o1.length; i++){
                // 모든 공항의 글자는 세 글자임
                for(int j=0; j<3; j++){
                    if(o1[i].charAt(j) != o2[i].charAt(j)){
                        return o1[i].charAt(j) - o2[i].charAt(j);
                    }
                }
            }
            return o1[1].charAt(0)- o2[1].charAt(0);
        });

        // 가장 우선이 되는 값 반환
        return ansList.get(0);
    }

    private static void dfs(String city, String str, int depth) {
        // 경로가 다 만들어졌을 경우
        if(depth == visited.length){
            ansList.add(str.split(" "));
            return;
        }

        // 현재 도시에서 출발할 수 없을 경우
        if(!map.containsKey(city)) return;

        for (int i = 0; i < map.get(city).size(); i++) {
            Node nn = map.get(city).get(i);

            // 아직 사용하지 않은 항공권일 경우
            if(!visited[nn.location]){
                visited[nn.location] = true;
                dfs(nn.city, str +" "+nn.city, depth+1);
                visited[nn.location] = false;
            }
        }
    }
}