[프로그래머스 / Level3] 여행경로 (Java)

문제 보기

사용한 것

• 가능한 경로를 구하기 위한 DFS
• key : 출발지, value : 목적지들 저장하기 위한 HashMap

풀이 방법

• map에 출발지, 목적지 정보를 저장한다.
• 문제 조건에 맞게 dfs를 출발지에 "ICN"부터 넣어 시작한다.
• map에 출발지로 목적지들을 꺼낸다.
• 목적지들마다 티켓을 사용하여 해당 목적지를 출발지로 depth를 1 증가시켜 재귀 돌린다.
• depth가 티켓의 개수와 동일해지면 티켓을 전부 사용한 것이므로 재귀를 중단한다.
• answer가 비어있으면 그 동안의 경로를 기록한 path를 깊은 복사 해준다.
• answer이 존재하면 path가 사전 순으로 더 빠르면 answer을 교체한다.

코드

class Solution {

    int N;
    String[] answer;
    Map<String, List<String>> map = new HashMap<>();

    public String[] solution(String[][] tickets) {
        N = tickets.length;
        for (int i = 0; i < tickets.length; i++) {
            String[] ticket = tickets[i];
            String from = ticket[0];
            String to = ticket[1];

            if (!map.containsKey(from)) {
                List<String> list = new ArrayList<>();
                list.add(to);
                map.put(from, list);
            } else {
                map.get(from).add(to);
            }
        }

        String[] path = new String[N + 1];
        path[0] = "ICN";
        dfs(0, "ICN", path);

        return answer;
    }

    void dfs(int depth, String from, String[] path) {
        if (depth == N) {
            if (answer == null) {
                answer = new String[N + 1];
                for (int i = 0; i < N + 1; i++) {
                    answer[i] = path[i];
                }
            } else {
                for (int i = 0; i < N + 1; i++) {
                    if (path[i].compareTo(answer[i]) < 0) {
                        break;
                    } else if (path[i].compareTo(answer[i]) > 0) {
                        return;
                    }
                }
                for (int i = 0; i < N + 1; i++) {
                    answer[i] = path[i];
                }
            }

            return;
        }

        if (!map.containsKey(from)) {
            return;
        }

        List<String> list = map.get(from);
        for (int i = 0; i < list.size(); i++) {
            String to = list.get(0);
            path[depth + 1] = to;
            list.remove(to);
            dfs(depth + 1, to, path);
            list.add(to);
        }
    }
}