프로그래머스 Level 3 – 여행경로(Java, DFS 백트래킹) 풀이

✈️ 프로그래머스 Level 3 – 여행경로(Java, DFS 백트래킹) 풀이

오늘은 프로그래머스에서 정말 자주 등장하는 그래프/백트래킹 문제,
바로 “여행경로” 문제를 정리해봤다.

이 문제의 핵심은 아주 단순하다.

주어진 항공권들을 모두 사용해서 만들 수 있는 경로 중
사전순으로 가장 앞서는 경로를 찾는 것.

그래서 DFS + 백트래킹을 이용해
"항공권을 사용했다가 다시 되돌리기" 작업을 하면서
모든 경우의 수를 탐색한다.

---

📌 문제 핵심 포인트

✔️ 1. 항상 "ICN"에서 출발

문제에서 출발점이 고정되어 있다.

✔️ 2. 티켓을 사전순으로 정렬해야 함

왜?
→ DFS 진행 중 여러 경로가 생기는데,
사전순으로 정렬해두면 가장 먼저 완성되는 경로가 곧 정답이기 때문이다.

✔️ 3. 모든 티켓을 사용했을 때가 종료 조건

티켓 개수가 N일 때
도착 경로의 길이는 N+1이 되어야 한다.

✔️ 4. DFS + 백트래킹

• 티켓을 사용하면 vist[i] = true
• 탐색이 끝났는데 답이 안 되면 다시 vist[i] = false 로 되돌림
• 전체 경로가 완성되는 순간 더 이상 탐색할 필요 없이 바로 종료

---

🧠 풀이 흐름

1. 티켓 배열을 출발지 → 도착지 기준으로 사전순 정렬
2. DFS 시작
3. 방문하지 않은 티켓 중
   출발지가 현재 위치와 같은 티켓만 탐색
4. 해당 티켓을 선택 → 다음 도시로 이동
5. 모든 티켓을 사용했다면 정답 확정
6. 정답이 나오면 더 이상 다른 경로 탐색하지 않도록 chk 플래그로 가지치기

---

🧩 자바 코드 (DFS 백트래킹)

 

import java.util.*;

class Solution {
    boolean chk = false;
    
    public String[] solution(String[][] tickets) {
        String[] answer = new String[tickets.length + 1];
        
        Arrays.sort(tickets, (a, b) -> {
            int s = a[0].compareTo(b[0]);
            if (s == 0) return a[1].compareTo(b[1]);
            return s;
        });
        
        boolean[] vist = new boolean[tickets.length];
        answer[0] = "ICN";
        
        dfs(tickets, answer, vist, 0, "ICN");
        return answer;
    }
    
    private void dfs(String[][] tickets, String[] answer, boolean[] vist, int dist, String con) {
        if (chk) return;
        
        if (dist == tickets.length) {
            chk = true;
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!vist[i] && tickets[i][0].equals(con)) {
                answer[dist + 1] = tickets[i][1];
                vist[i] = true;
                
                dfs(tickets, answer, vist, dist + 1, tickets[i][1]);
                if (chk) return;
                
                vist[i] = false;
            }
        }
    }
}

---

🎯 정리

이 문제는 그래프 탐색 + 백트래킹 + 사전순 정렬
이 세 가지를 모두 요구하는 좋은 문제다.

특히,
정답을 찾은 순간 탐색을 끊는 가지치기(chk) 처리가
시간 초과를 막는 핵심 포인트다.

코테에서 DFS/백트래킹 문제를 연습하고 싶다면
반드시 한 번은 풀어봐야 할 문제라고 생각한다.