[C++] 프로그래머스/3/43164. 여행경로

여행경로 (프로그래머스 Level 3 - 43164)

1. 문제 설명

주어진 항공권 정보 tickets를 바탕으로 "ICN"에서 출발하는 여행 경로를 찾되,
모든 항공권을 한 번씩 사용하면서 사전 순으로 가장 앞선 경로를 구해야 한다.

• 항공권 정보는 [출발지, 도착지] 형식
• 경로는 항공권을 모두 사용한 순서대로 나열한 공항명 벡터

2. 핵심 아이디어

• 모든 항공권을 순회해야 하므로 DFS 백트래킹 사용
• 사전순으로 가장 앞선 경로를 반환하기 위해 티켓 목록을 정렬
• 경로가 완성되면 그 순간 바로 answer에 저장하고 리턴
• 이미 경로를 찾았다면 더 이상 탐색하지 않도록 !answer.empty() 체크로 조기 탈출

3. 코드 설명

DFS

void dfs(vector<vector<string>>& tickets, int depth) {
    if (depth == tickets.size()) {
        answer = path;
        return;
    }

    for (int i = 0; i < tickets.size(); ++i) {
        if (!visited[i] && tickets[i][0] == path.back()) {
            visited[i] = 1;
            path.push_back(tickets[i][1]);
            dfs(tickets, depth + 1);
            if (!answer.empty()) return; // 사전순 최소 경로면 바로 리턴
            path.pop_back();
            visited[i] = 0;
        }
    }
}

• depth == tickets.size()이면 모든 티켓 사용 완료 → path를 answer로 복사
• 현재 위치가 path.back()인 티켓만 탐색
• 재귀적으로 다음 도시로 이동
• 경로를 찾은 경우 백트래킹을 멈춘다

전체 코드

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

using namespace std;
vector<string> answer,path;
vector<int> visited;

void dfs(vector<vector<string>>& tickets, int depth) {
    if (depth == tickets.size()) {
        answer = path;
        return;
    }

    for (int i = 0; i < tickets.size(); ++i) {
        if (!visited[i] && tickets[i][0] == path.back()) {
            visited[i] = 1;
            path.push_back(tickets[i][1]);
            dfs(tickets, depth + 1);
            if (!answer.empty()) {
                return;
            }
            path.pop_back();
            visited[i] = 0;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    visited.resize(tickets.size(), 0);
    path = {"ICN"};

    sort(tickets.begin(), tickets.end());
    dfs(tickets, 0);

    return answer;
}