99클럽 코테 스터디 12일차 TIL: [프로그래머스] 여행경로

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

프로그래머스

 

처음에 푼 풀이는 다음과 같다. 

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            PriorityQueue<String> que = map.getOrDefault(ticket[0], new PriorityQueue<String>());
            que.add(ticket[1]);
            map.put(ticket[0], que);
        }
        
        List<String> list = new ArrayList<>();
        list.add("ICN");
        String key = "ICN";
        while (map.containsKey(key)) {
            if (map.get(key).isEmpty()) break;
            String next = map.get(key).poll();
            list.add(next);
            key = next;
        }
        
        String[] answer = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}

 

그런데 제출하니 1, 2번에서 틀렸다. 문제를 살펴보면 "모든 도시를 방문할 수 없는 경로는 주어지지 않습니다."라고 나와있다. 그리고 티켓을 모두 사용해야 한다고 한다. 따라서 나는 모든 도시를 이어서 방문하게 될 것이라고 생각해서 위처럼 풀었다. 그러나 다음과 같은 반례가 있다.

• [["ICN", "AAA"], ["ICN", "BBB"], ["BBB", "ICN"]]

내 풀이대로면 위 반례에서 답에 ["ICN", "AAA"]가 되고 모든 티켓을 사용하지 않게 된다. 따라서 dfs를 사용해야 한다. 

• dfs를 통해 가능한 경로의 경우의 수를 모두 탐색한다.
• 그리고 각각의 경로를 answerList에 담고, 정렬 후 첫번째 값이 답이 된다. (알파벳 순)

import java.util.*;

class Solution {
    
    List<String> answerList = new ArrayList<>();
    String[][] tickets;
    boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        this.visited = new boolean[tickets.length];
        
        dfs(0, "ICN", "ICN");
        Collections.sort(answerList);
        return answerList.get(0).split(", ");
    }
    
    public void dfs(int cnt, String start, String answer) {
        
        if (cnt == tickets.length) {
            answerList.add(answer);
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!start.equals(tickets[i][0])) continue;
            if (visited[i]) continue; // 이미 사용한 티켓이면 패스
            visited[i] = true;
            dfs(cnt + 1, tickets[i][1], answer + ", " + tickets[i][1]);
            visited[i] = false;
        }
    }
}

 

위 풀이는 tickets.length만큼의 depth로 dfs를 진행하기 때문에 무조건 모든 티켓을 다 사용하게 된다. 따라서 반례에 답이 ["ICN", "BBB", "ICN", "AAA"]가 된다.