[Programmers/C++] 여행경로

시간 복잡도

• DFS를 이용해 모든 경우의 수를 탐색하므로 최악의 경우 $O(N!)$이 발생할 수 있습니다.
• N이 최대 10,000 이기 때문에 시간초과가 발생할 수 있어 최적화가 필요합니다.

문제 접근법

• DFS를 이용해 모든 경우의 수를 탐색해도 되지만 최악의 경우 시간 초과가 발생할 수 있습니다.
• 그래프를 해시맵 + 우선순위 큐를 사용하여 알파벳이 빠른 순서로 빠르게 탐색할 수 있고 DFS를 스택을 이용하여 구현하면 $O(NlogN)$의 시간 복잡도로 구현할 수 있습니다.
• Eulerian Path(유러 경로) 방식을 이용하여 더 이상 방문할 노드가 없을 때 경로를 확정하는 방식으로 불필요한 백트래킹을 방지할 수 있습니다.

코드

개선된 방법

#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
    unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
    
    for (auto& ticket : tickets) {
        graph[ticket[0]].push(ticket[1]);
    }

    vector<string> answer;
    stack<string> s;
    s.push("ICN"); 

    while (!s.empty()) {
        string node = s.top();
        
        if (graph[node].size() > 0) {
            string next = graph[node].top();
            graph[node].pop();
            s.push(next);
        } 
        else {
            answer.push_back(node);
            s.pop();
        }
    }

    reverse(answer.begin(), answer.end());
    
    return answer;
}

DFS 풀이

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

using namespace std;

static vector<string> answer;
bool flag = false;
bool visited[10001]={};

void DFS(vector<vector<string>>& tickets, string node, int depth)
{
    if(depth == tickets.size())
    {
        flag = true;
    }
    
    answer.push_back(node);
    for(int i=0; i<tickets.size(); i++)
    {
        if(!visited[i] && tickets[i][0]==node)
        {
            visited[i]=true;
            DFS(tickets, tickets[i][1], depth+1);
            
            if(!flag)
            {
                answer.pop_back();
                visited[i]=false;
            }
        }
    }
    
}

vector<string> solution(vector<vector<string>> tickets) {

    sort(tickets.begin(), tickets.end());
    
    DFS(tickets, "ICN", 0);
    
    return answer;
}