[프로그래머스][C++] 여행경로

여행경로

문제 링크

여행경로

분석

주어진 항공권을 모두 사용하여 가능한 여행 경로 중 사전 순으로 가장 빠른 경로를 찾는 문제입니다.

tickets은 2차원 배열로 [출발지, 도착지] 형식을 가진 항공권 정보를 의미합니다.

문제의 조건은 다음과 같습니다.

• 모든 항공권을 모두 사용해야 합니다.
• 여행은 항상 "ICN"공항에서 시작합니다.
• 가능한 경로가 여러 개일 경우, 알파벳 순으로 앞서는 경로를 선택합니다.
• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

여행 경로를 배열로 반환해야 합니다.

깊이 우선 탐색(DFS)과 백트래킹으로 문제를 풀어낼 수 있습니다.

풀이

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

using namespace std;

// 정답 경로를 저장하는 전역 변수
vector<string> answer;

// DFS로 가능한 경로를 탐색하며, 모든 티켓을 사용하는 경로 중 사전 순으로 가장 빠른 경로를 찾는다.
// 매개변수는 순서대로, 항공권 목록, 티켓 사용 여부, 현재까지의 경로, 사용한 티켓 수, 현재 공항 코드
void dfs(const vector<vector<string>>& tickets, vector<bool>& visited, vector<string>& path, 
         int depth, string curTicket)
{
    // 현재 공항 추가
    path.push_back(curTicket);
    
    // 모든 티켓을 사용한 경우 정답 경로를 저장하고 종료한다.
    if (depth == tickets.size())
    {
        answer = path;
        return;
    }
    // 이미 정답이 구해졌으면 더 이상 탐색하지 않는다.
    else if (!answer.empty())
    {
        return;
    }
    
    // 현재 공항에서 출발 가능한 티켓들을 순회한다.
    for (int i = 0; i < tickets.size(); ++i)
    {
        if (!visited[i] && tickets[i][0] == curTicket)
        {
            visited[i] = true;
            
            // 다음 공항으로 DFS 재귀 호출
            dfs(tickets, visited, path, depth + 1, tickets[i][1]);
            
            // 백트래킹
            visited[i] = false;
        }
    }
    
    // 백트래킹
    path.pop_back();
}

// 출발지가 같으면 도착지 기준으로 사전순 정렬한다.
bool compare(const vector<string>& a, const vector<string>& b)
{
    if (a[0] == b[0])
    {
        return a[1] < b[1];
    }
    
    return a[0] < b[0];
}

vector<string> solution(vector<vector<string>> tickets) {
    // 가능한 경로를 사전순으로 만들기 위해 티켓 정렬
    sort(tickets.begin(), tickets.end(), compare);
    
    // 티켓 사용 여부 벡터 초기화
    vector<bool> visited(tickets.size(), false);
    // 경로 기록용 벡터
    vector<string> path;
    
    // "INC"공항을 시작으로 DFS 호출
    dfs(tickets, visited, path, 0, "ICN");
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n \ log \ n + n^2)$입니다.

• 정렬 함수 $O(n \ log \ n)$
• DFS 탐색 평균적으로 $O(n^2), 최악의 경우 $O(n!)$
• $O(n \ log \ n) + O(n^2)$

공간 복잡도는 $O(n)$입니다.

• 티켓 사용 여부를 저장하는 visited $O(n)$
• 경로를 기록하는 path $O(n + 1)$
• 정답 경로를 저장하는 answer $O(n + 1)$
• DFS 재귀 호출 스택 $O(n)$
• $O(n) + O(n + 1) + O(n + 1) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.03ms, 4.12MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 4.19MB)
테스트 4 〉 통과 (0.01ms, 4.13MB)