[프로그래머스] 여행경로 (java)

🔗 문제링크

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

👩🏻‍💻 코드

import java.util.*;

class Solution {
    static List<String> answer = new ArrayList<>();
    static String route = "";
    static boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(tickets, "ICN", 0);

        Collections.sort(answer);
        return answer.get(0).split(",");
    }
    
    public static void dfs(String[][] tickets, String end, int cnt) {
        route += end + ",";

        if (cnt == tickets.length) {
            answer.add(route);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            String next_s = tickets[i][0];
            String next_e = tickets[i][1];
            if (next_s.equals(end) && !visited[i]) {
                visited[i] = true;
                dfs(tickets, next_e, cnt + 1);
                visited[i] = false;
                route = route.substring(0, route.length() - 4);
            }
        }
    }
}

📝 정리

dfs를 쓰면 되는데 어렵게 생각한 것 같다.
ICN으로 시작해서 end 포인트와 start 포인트가 같은 것을 tickets 배열에서 찾아주면 되었다.

참고 링크
https://velog.io/@jwkim/DFS-travel-route