[Algorithm: DFS] 프로그래머스 <여행경로>

DFS 백트래킹 Java Programmers Lv.3

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=java

프로그래머스

 

---

 

문제 설명

항공권 목록이 주어질 때, ICN에서 출발해서 모든 항공권을 한 번씩 사용하는 여행 경로를 반환하는 문제다. 가능한 경로가 여러 개라면 알파벳 순서가 앞서는 경로를 선택한다.

tickets	return
[["ICN","JFK"],["HND","IAD"],["JFK","HND"]]	["ICN","JFK","HND","IAD"]
[["ICN","SFO"],["ICN","ATL"],["SFO","ATL"],["ATL","ICN"],["ATL","SFO"]]	["ICN","ATL","ICN","SFO","ATL","SFO"]

 

 

문제 핵심 파악

이 문제에는 두 가지 조건이 동시에 걸려 있다.

조건 1. 모든 항공권을 정확히 한 번씩 사용해야 한다.
조건 2. 경로가 여러 개일 때 알파벳 순서가 앞서는 경로를 선택한다.

• 조건 1 때문에 단순 BFS/DFS로는 부족하다. 한 방향으로 갔다가 막히면 돌아와야(백트래킹) 하는 구조가 필요하다.
• 조건 2는 탐색 전에 티켓을 정렬해두면 자연스럽게 해결된다.

왜 단순 DFS로 안 되는가?
예시 2에서 ICN → SFO를 먼저 선택하면 나머지 티켓을 모두 소비하지 못하는 막힌 경로가 생긴다.
이런 경우 되돌아가서(백트래킹) 다른 선택지를 시도해야 한다.

 

 

---

 

 

전략: 정렬 + DFS + 백트래킹

1

티켓을 사전순으로 정렬 — 알파벳 순으로 탐색하면 가장 먼저 완성되는 경로가 정답

2

DFS로 경로 탐색 — 현재 공항에서 출발하는 미사용 티켓을 순서대로 선택

3

백트래킹 — 모든 티켓을 소비하지 못하면 되돌아가 다른 티켓을 시도

4

조기 종료 — result != null이면 이미 정답을 찾은 것이므로 즉시 반환

 

 

① 정렬 — 알파벳 순 보장

티켓을 출발지 → 도착지 기준으로 사전순 정렬한다. 이렇게 하면 DFS가 항상 알파벳 순서로 경로를 시도하게 되어, 가장 먼저 완성되는 경로가 곧 알파벳 순 최선이 된다.

예시 2 정렬 전후 비교

정렬 전

ICN→SFO

ICN→ATL

SFO→ATL

ATL→ICN

ATL→SFO

정렬 후 (출발지 → 도착지 사전순)

ATL→ICN

ATL→SFO

ICN→ATL

ICN→SFO

SFO→ATL

ICN에서 출발하는 티켓 중 ATL이 SFO보다 앞에 위치 → DFS는 ATL을 먼저 시도

 

 

② DFS + 백트래킹 동작 시각화

예시 2를 단계별로 추적해보자. 정렬된 티켓 기준으로 DFS가 어떻게 진행되는지 확인한다.

정렬된 티켓 (인덱스 기준)

0 ATL→ICN

1 ATL→SFO

2 ICN→ATL

3 ICN→SFO

4 SFO→ATL

DFS 탐색 경로 (성공 루트)

dfs("ICN", count=0)

ICN

ICN 출발 티켓 중 idx=2 (ICN→ATL)를 먼저 선택

dfs("ATL", count=1)   티켓[2] 사용

ICN → ATL

ATL 출발 티켓 중 idx=0 (ATL→ICN)를 먼저 선택

dfs("ICN", count=2)   티켓[0] 사용

ICN → ATL → ICN

ICN 출발 티켓 중 idx=3 (ICN→SFO)만 남음

dfs("SFO", count=3)   티켓[3] 사용

ICN → ATL → ICN → SFO

SFO 출발 티켓 idx=4 (SFO→ATL) 선택

dfs("ATL", count=4)   티켓[4] 사용

ICN → ATL → ICN → SFO → ATL

ATL 출발 티켓 idx=1 (ATL→SFO) 선택

dfs("SFO", count=5)   count == tickets.length → 완성!

ICN → ATL → ICN → SFO → ATL → SFO

result 저장 후 즉시 반환

 

③ 백트래킹이 필요한 이유

만약 ICN에서 SFO(idx=3)를 먼저 선택했다면 어떻게 될까? 예시 2로 확인해보자.

❌ 막히는 경우 — ICN → SFO를 먼저 선택

1

ICN → SFO 선택 (idx=3 사용)

ICN → SFO

2

SFO → ATL 선택 (idx=4 사용)

ICN → SFO → ATL

3

ATL → ICN 선택 (idx=0 사용)

ICN → SFO → ATL → ICN

4

ICN → ATL 선택 (idx=2 사용)

ICN → SFO → ATL → ICN → ATL

5

ATL에서 출발하는 미사용 티켓: idx=1 (ATL→SFO) 사용 → SFO 도착
SFO에서 출발하는 미사용 티켓 없음 → 막힘! count=5이지만 티켓이 하나 남음

→ 백트래킹: 사용한 티켓 반납, 경로에서 제거하고 다른 선택지로 복귀

백트래킹 핵심 코드:
visited[i] = false; — 티켓 반납
answer.remove(answer.size() - 1); — 경로에서 마지막 공항 제거

 

 

④ 조기 종료 — result != null

정렬 덕분에 가장 먼저 완성된 경로가 알파벳 순 정답이다. 따라서 result에 값이 저장되는 순간 더 이상 탐색할 필요가 없다.

// dfs 호출 후 result가 채워졌다면 더 이상 탐색 불필요
dfs(tickets[i][1], tickets, count + 1);

if (result != null) return;   // 정답 발견 → 즉시 상위 호출로 전파

// result가 null이면 백트래킹
visited[i] = false;
answer.remove(answer.size() - 1);

result != null 체크가 없으면 정답을 찾은 이후에도 다른 경로를 계속 탐색하면서
result를 덮어써버릴 수 있다. 조기 종료는 정확성과 성능 모두를 위한 장치다.

 

 

---

 

전체 코드

import java.util.*;

class Solution {
    boolean[] visited;
    ArrayList<String> answer = new ArrayList<>();
    String[] result;

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

        // 출발지 → 도착지 기준 사전순 정렬
        Arrays.sort(tickets, (a, b) -> {
            if (a[0].equals(b[0])) return a[1].compareTo(b[1]);
            return a[0].compareTo(b[0]);
        });

        answer.add("ICN");          // 출발지 고정
        dfs("ICN", tickets, 0);

        return result;
    }

    void dfs(String current, String[][] tickets, int count) {
        if (count == tickets.length) {  // 모든 티켓 사용 완료
            result = answer.toArray(new String[0]);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(current)) {

                visited[i] = true;                     // 티켓 사용
                answer.add(tickets[i][1]);              // 경로 추가

                dfs(tickets[i][1], tickets, count + 1);

                if (result != null) return;           // 정답 발견 → 조기 종료

                visited[i] = false;                    // 백트래킹: 티켓 반납
                answer.remove(answer.size() - 1);      // 백트래킹: 경로 제거
            }
        }
    }
}

 

 

 

---

 

정리

사전순 정렬

DFS가 항상 알파벳 순으로 탐색 → 가장 먼저 완성된 경로가 정답. 별도 비교 불필요.

visited 배열

티켓 index 기반으로 사용 여부 관리. 같은 구간의 중복 티켓도 개별로 처리 가능.

백트래킹

막힌 경로에서 visited=false, answer.remove()로 상태를 되돌려 다른 선택지를 탐색.

result != null 조기 종료

정답 발견 즉시 모든 재귀 호출을 탈출. 정확성과 성능을 동시에 보장.

"정렬 → DFS → 백트래킹 → 조기 종료"의 4단계 패턴은
순열/조합 탐색, 모든 경우를 시도해야 하는 문제에서 반복적으로 등장한다.
특히 조건을 만족하는 첫 번째 경우를 구하는 문제에서 백트래킹 + 조기 종료 조합은 핵심이다.

 

 

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.