프로그래머스: 여행경로(JAVA)

문제 요약

• "ICN" 공항에서 시작
• 모든 티켓을 한 번씩만 사용하여 여행경로를 만들어야 함
• 가능한 경로가 여러 개일 경우, 알파벳 순서가 앞서는 경로를 리턴

---

풀이

1. 정렬: 사전 순서대로 정답이 나오게 하기 위해 목적지 기준으로 먼저 정렬합니다.
2. DFS 탐색:
   • 티켓을 하나씩 사용하며 다음 목적지로 이동
   • 모든 티켓을 사용한 경우, 현재 경로를 정답으로 반환
3. 백트래킹: 경로가 유효하지 않으면 되돌아가 다른 경로를 탐색

---

JAVA 코드

import java.util.*;

class Solution {

    static boolean[] visited;
    static List<String> route = new ArrayList<>();

    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];

        // 목적지 기준 정렬 (사전순 경로 탐색을 위함)
        Arrays.sort(tickets, (a, b) -> a[1].compareTo(b[1]));

        route.add("ICN"); // 항상 ICN에서 출발

        return dfs("ICN", tickets, 0).toArray(new String[0]);
    }

    static List<String> dfs(String now, String[][] tickets, int count) {
        if (count == tickets.length) {
            // 모든 티켓을 사용했다면 현재 경로가 정답
            return new ArrayList<>(route);
        }

        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(now)) {
                visited[i] = true;
                route.add(tickets[i][1]);

                List<String> result = dfs(tickets[i][1], tickets, count + 1);
                if (result != null) return result;

                // 백트래킹
                visited[i] = false;
                route.remove(route.size() - 1);
            }
        }

        return null;
    }
}

 

 

왜 result != null일 때 return?

List<String> result = dfs(...);
if (result != null) return result;

• 모든 티켓을 사용한 경로가 나왔을 때만 result가 null이 아닌 값을 반환
• 그 외는 다른 경로를 계속 탐색해야 하므로 null이 리턴됨
• 첫 번째로 찾은 유효한 경로가 바로 최적해이므로 즉시 반환

---

String vs Integer 정렬 차이

• 문자열 비교: a[1].compareTo(b[1])
• 숫자 비교: a - b

---

toArray(new String[0]) 쓰는 이유

return list.toArray(new String[0]);

 

• List<String> → String[] 변환
• 타입 안정성과 성능을 고려할 때, new String[0]을 넘기는 것이 Java에서 가장 효율적인 패턴