[DAY93] Algorithm : Travel Route

주어진 항공권을 모두 사용하여 여행 경로를 짜는 문제다. 모든 티켓을 소모해야 하며, 가능한 경로가 여러 개일 경우 알파벳 순서가 앞서는 경로를 선택해야 한다. DFS(깊이 우선 탐색)를 통해 경로를 깊게 탐색하되, 막힌 길이 나오면 다시 돌아오는 백트래킹(Backtracking) 기법이 필수적이다.

---

❓ 문제 분석

• 목표: 주어진 티켓을 모두 소모하여 만들 수 있는 경로 중, 알파벳 순서가 가장 빠른 경로 반환.
• 제약 조건:
  • 티켓 개수 $N$: 최대 10,000.
  • "주어진 항공권은 모두 사용해야 합니다" $\rightarrow$ 단순 방문(Visited Node)이 아니라 간선 소모(Used Edge) 여부를 체크해야 한다.
  • 경로가 끊기면 안 되므로, 잘못된 길에 들어섰을 때 다시 돌아오는 로직이 필요하다.
• 핵심 키워드: "ICN 출발", "모두 사용", "알파벳 순서 앞서는"

---

💡 풀이 설계

1. 시도했던 접근 (Intuition)

• 처음엔 단순히 현재 위치에서 갈 수 있는 공항 중 알파벳이 가장 빠른 곳으로 이동하면 된다고 생각했다. (Greedy)
• 하지만, 알파벳이 빠른 곳으로 갔다가 티켓이 끊겨서 모든 티켓을 못 쓰는 경우가 발생할 수 있다. 따라서 "일단 가보고, 안 되면 되돌아오는" 전략이 필요하다.

2. 최종 해결책 (DFS + Backtracking)

• 전략: 모든 경로를 깊게 탐색하는 DFS를 사용한다.
• 핵심 로직:
  1. 정렬(Sorting): tickets 배열을 미리 오름차순 정렬한다. 이렇게 하면 그래프 생성 시 자동으로 도착지가 알파벳 순으로 저장되어, DFS 탐색 순서가 자연스럽게 사전순이 된다.
  2. 그래프 생성: unordered_map과 vector를 사용해 인접 리스트를 만든다. 이때 중복 티켓(예: ICN->NRT가 2장)을 구분하기 위해 티켓의 고유 인덱스도 함께 저장한다.
  3. DFS & Backtracking:
     • 경로에 공항을 추가하고 티켓을 사용 처리(visited = true)한다.
     • 만약 모든 티켓을 다 썼다면(기저 조건), 그 경로가 정답이다.
     • 만약 길이 막혔다면, 다시 경로에서 빼고 티켓을 미사용 처리(visited = false)하여 다른 길을 찾는다.
• 종료 조건: 경로에 담긴 공항의 수가 티켓 수 + 1개가 되면 탐색을 즉시 종료한다.

---

💻 코드 구현

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<bool> visited;
vector<string> answer;
bool found = false;

void dfs(string current, vector<string>& routes, vector<vector<string>>& tickets, 
         unordered_map<string, vector<pair<string, int>>>& adj) {
    
    // 1. 모든 티켓을 사용했으면 정답 저장 후 종료
    if (routes.size() == tickets.size() + 1) {
        answer = routes;
        found = true;
        return;
    }

    // 2. 현재 공항에서 갈 수 있는 경로 탐색
    for (auto& nextInfo : adj[current]) {
        if (found) return; // 이미 최적의 경로(알파벳 순)를 찾은 경우

        string nextAirport = nextInfo.first;
        int ticketIdx = nextInfo.second;

        // 3. 사용하지 않은 티켓인 경우만 방문
        if (!visited[ticketIdx]) {
            visited[ticketIdx] = true;
            routes.push_back(nextAirport);
            
            dfs(nextAirport, routes, tickets, adj);
            
            // 4. 백트래킹: 정답이 완성되지 않았다면 상태 복구
            if (!found) {
                routes.pop_back();
                visited[ticketIdx] = false;
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    // 알파벳 순 정렬 (DFS 진입 시 자동으로 사전순 탐색)
    sort(tickets.begin(), tickets.end());

    // 그래프 생성 (출발지별 목적지 리스트)
    unordered_map<string, vector<pair<string, int>>> adj;
    for (int i = 0; i < (int)tickets.size(); i++) {
        adj[tickets[i][0]].push_back({tickets[i][1], i});
    }

    visited.assign(tickets.size(), false);
    vector<string> routes = {"ICN"}; // 시작점 "ICN" 고정
    
    dfs("ICN", routes, tickets, adj);

    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: 처음에는 방문 여부를 adj 맵에서 해당 원소를 삭제하는 방식으로 구현하려 했으나, 백트래킹 시 다시 복구하는 과정이 복잡하고 비효율적이었다.
• 해결: 티켓마다 고유 인덱스(0, 1, 2...)를 부여하고, 단순한 vector<bool> visited 배열로 사용 여부를 관리하니 로직이 훨씬 깔끔해졌다.
• 정렬 이슈: dfs 내부에서 매번 정렬하면 시간 초과가 날 수 있다. 처음에 tickets 전체를 한 번만 정렬해두면, 그래프를 만들 때 순서가 유지되므로 효율적이다.

---

✅ 오늘의 회고

항목	내용
유형	DFS (깊이 우선 탐색), Backtracking
체감 난이도	상 (백트래킹 로직과 상태 복구 시점이 헷갈림)
복잡도	시간: $O(N \log N)$ (정렬), 공간: $O(N)$
새로 배운 것	백트래킹의 정석 패턴: Mark $\rightarrow$ DFS $\rightarrow$ Unmark. 그리고 found 플래그를 이용해 불필요한 탐색을 조기에 종료하는 최적화 방법.