[프로그래머스] 여행 경로 (오일러 경로)

문제 소개

이전 풀었던 여행경로 - 프로그래머스 문제를 다른 알로리즘으로 정리합니다.
이 문제는 모든 항공권을 한 번씩 사용하면서, 사전순으로 가장 앞선 경로를 찾는 그래프 탐색 문제입니다.
핵심은 모든 간선을 정확히 한 번씩 사용해야 하고, 가능한 경로 중 사전순으로 가장 앞서는 경로를 고르는 것입니다.

문제 링크: 여행경로 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 티켓 정보를 그래프 형태 (출발지 → 도착지 리스트) 로 구성
2. 도착지 리스트는 사전순 우선 탐색을 위해 PriorityQueue 사용
3. DFS를 이용해 경로 탐색하되, 모든 티켓을 한 번씩 사용하면서 돌아가는 경로 구성
4. 탐색이 끝날 때마다 역순으로 경로 추가 (addFirst)

---

해결 과정 및 코드

핵심 아이디어

1. 모든 티켓을 한 번씩만 사용해야 하므로, 모든 간선을 정확히 한 번씩 지나는 오일러 경로(Eulerian Path) 조건과 유사
2. 사전순 탐색을 보장하기 위해 PriorityQueue 사용
3. DFS 재귀가 끝나고 나서 경로를 추가하면, 탐색 완료 기준으로 역순 경로가 완성됨
4. 최종 경로는 LinkedList에 저장한 뒤 배열로 변환

코드

시간 복잡도 : O(N log N) (PQ에 티켓삽입(O(NlogN) + DFS:O(N log N) )

import java.util.*;

class Solution {
    Map<String, PriorityQueue<String>> graph = new HashMap<>();
    LinkedList<String> path = new LinkedList<>();

    public String[] solution(String[][] tickets) {
        for (String[] ticket : tickets) {
            graph.computeIfAbsent(ticket[0], k -> new PriorityQueue<>())
                 .add(ticket[1]);
        }

        dfs("ICN");

        return path.toArray(new String[0]);  // 최종 결과를 배열로 반환
    }

    void dfs(String airport) {
        PriorityQueue<String> arrivals = graph.get(airport);

        while (arrivals != null && !arrivals.isEmpty()) {
            dfs(arrivals.poll());  // 사전순 도착지 먼저 방문
        }

        path.addFirst(airport);  // 경로 역추적 저장
    }
}

 

### Stack 기반 구현

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        // 그래프 초기화 (사전순 유지를 위해 PriorityQueue 사용)
        Map<String, PriorityQueue<String>> graph = new HashMap<>();

        for (String[] ticket : tickets) {
            graph.computeIfAbsent(ticket[0], k -> new PriorityQueue<>()).add(ticket[1]);
        }

        ArrayDeque<String> stack = new ArrayDeque<>();
        LinkedList<String> route = new LinkedList<>();

        stack.push("ICN");

        while (!stack.isEmpty()) {
            String curr = stack.peek();
            PriorityQueue<String> arrivals = graph.get(curr);

            // 더 이상 갈 곳이 없다면 경로에 추가 (역순)
            if (arrivals == null || arrivals.isEmpty()) {
                route.addFirst(curr);
                stack.pop();
            } else {
                stack.push(arrivals.poll()); // 사전순 도착지 먼저 탐색
            }
        }

        return route.toArray(new String[0]);
    }
}

---

동작 예시

🎟 입력 티켓

[["ICN", "BBB"], ["BBB", "ICN"], ["ICN", "AAA"]]

---

1. 그래프 구성 (사전순 정렬됨 → PriorityQueue 사용)

"ICN" → ["AAA", "BBB"]
"BBB" → ["ICN"]

---

2. DFS 실행 흐름

0) 시작: dfs("ICN")

• arrivals = ["AAA", "BBB"]
• 사전순 우선 → "AAA" 선택
  => dfs("AAA")

---

1) dfs("AAA")

• arrivals = null → 종료
  => addFirst("AAA")
• path: ["AAA"]

---

2) dfs("ICN") 복귀

• "AAA"는 사용됨
• "BBB" 남음
  => dfs("BBB")

---

3) dfs("BBB")

• arrivals = ["ICN"]
  => dfs("ICN")

---

4) dfs("ICN") (세 번째 호출)

• arrivals = [] → 모두 사용됨
  => addFirst("ICN")
• path: ["ICN", "AAA"]

---

5) dfs("BBB") 복귀

=> addFirst("BBB")

• path: ["BBB", "ICN", "AAA"]

---

6) dfs("ICN") 복귀 (최초)

=> addFirst("ICN")

• path: ["ICN", "BBB", "ICN", "AAA"]

---

✅ 최종 경로

["ICN", "BBB", "ICN", "AAA"]

---

✅ 티켓 사용 확인 => 모두 사용 완료

• ["ICN", "AAA"] ✅
• ["ICN", "BBB"] ✅
• ["BBB", "ICN"] ✅

---

정리 요약

DFS 순서	"ICN" → "AAA" → (backtrack) BBB → ICN"
사전순 선택	"AAA"가 "BBB"보다 앞서서 먼저 사용됨
DFS 종료 후	경로를 addFirst()로 역순 삽입
최종 경로	["ICN", "BBB", "ICN", "AAA"]

---

참고 개념

오일러 경로 (Eulerian Path)

• 모든 간선(티켓)을 정확히 한 번씩 사용하는 경로
• 단, 출발점과 도착점이 다를 수 있음
• 이 문제는 정확히 해당 조건과 일치:
  → 모든 티켓을 한 번씩 사용해야 하고, 하나의 연결된 경로로 모든 항공권을 소모해야 함
• 오일러 경로 구성 알고리즘 중 하나인 Hierholzer’s Algorithm은 DFS 기반으로 구현
  → 재귀 호출 후에 현재 노드를 경로에 추가 (역순 구성)