이번에 풀어본 문제는
프로그래머스 여행경로 입니다.

📕 문제 링크

❗️코드

import java.util.*;

class Solution {
    static Map<String, List<String>> map;
    static Map<String, Integer> ticketCount;
    static String resultString;
    static int resultSize;
    static boolean isDone;
    public String[] solution(String[][] tickets) {
        String[] answer;
        map = new HashMap<>();
        ticketCount = new HashMap<>();

        resultSize = tickets.length;

        for (String[] ticket : tickets) {
            String from = ticket[0];
            String to = ticket[1];
            String sum = from.concat(to);
            ticketCount.put(sum, ticketCount.getOrDefault(sum, 0) + 1);

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

        for (String key : map.keySet()) {
            Collections.sort(map.get(key));
        }

        dfs("ICN", "ICN", 1);

        answer = resultString.split(" ");
        return answer;
    }
    static void dfs(String from, String result, int resultCount) {
        if (!isDone) {
            if (resultCount == resultSize + 1) {
                resultString = result;
                isDone = true;
                return;
            }

            if (map.containsKey(from)) {
                List<String> getDest = map.get(from);
                for (String to : getDest) {
                    String ticket = from.concat(to);
                    int curCount = ticketCount.get(ticket);
                    if (curCount > 0) {
                        ticketCount.put(ticket, curCount - 1);
                        dfs(to, result + " " + to, resultCount + 1);
                        ticketCount.put(ticket, curCount);
                    }
                }
            }
        }
    }
}

📝 풀이

입력된 티켓을 모두 사용하여 여행 경로를 완성하는 문제입니다. 결과는 사전순으로 출력해야합니다.
우선 입력값을 이용해 모든 티켓경로를 HashMap에 담아줍니다. (key : 출발지, values(list) : 도착지)
그 과정에서, 방문처리를 위한 HashMap<String, Integer>에도 값을 채워줍니다. 처음에는 중복 티켓이 없을 것이라 생각하고, Set을 사용해 문자열을 조합한 방문처리를 진행했지만, 자꾸 틀려서 찾아보니 중복 티켓이 가능한 문제였다고 합니다. 따라서 Integer 값으로 카운트를 담아놓고, 이후 과정에서 여러 장의 티켓을 모두 소모할 수 있도록 해줍니다. 마지막으로, 입력된 모든 value들을 사전순으로 정렬해줍니다.
입력 데이터를 모두 정리했다면, dfs 탐색을 통해 ICN 을 시작으로 여행 경로를 만들어 나갑니다. 이미 정렬된 리스트를 기준으로 dfs 탐색을 진행하기 때문에, 가장 처음으로 완성된 결과가 정답 결과가 되며, isDone 이라는 flag 역할의 boolean 변수를 선언하여, 완성된 이후의 불필요한 반복을 제거해줍니다.
마지막으로 완성된 문자열을 answer 배열에 공백을 기준으로 잘라내면 해결할 수 있습니다.

📜 후기

생각보다 빨리 풀어서 기분 좋았는데, 제출시에 1, 2번 테스트케이스를 자꾸 통과하지 못해서 조금 애먹었습니다 ㅠ 스스로 반례를 찾아내는 연습을 항상 하려고 하는데, 생각보다 쉽지 않은 것 같네요..