23.09.19. 풀었던 문제들

Programmers Lv. 3 여행경로, 17분

 그냥 DFS 돌리면 되는 문제. 단 각각의 vertex가 string으로 표현되는 점과 [사용한 표]를 어떻게 표기할지에 대해 유의해야 한다. 뭐.. 정석 DFS처럼 각 ticket의 index를 visit했는지 안했는지를 표기할 수 있긴 한데. 결국 alphabet 순서로 DFS + edges를 만들어야 하기 때문에 map을 사용해야 할 것 같다.

 처음에는 multiset을 썼었는데, DFS를 위해 multiset에서 element를 빼고 넣는 과정에서 계속 같은 위치를 참조하는 것 같았다. (무한루프) 그래서 map of map을 썼다. edges[i]는 i에 인접한 공항들의 map 목록이고, 이것은 [도착지 이름, 같은 표가 몇 개인지]를 나타낸다.

 나머지는 뭐.. 코드 보면 이해하기 쉬울 것 같다.

int max_depth;
map<string, map<string, int>> edges; // edges[i] : i에 인접한 공항들
vector<string> result;
 
bool DFS(int cur_depth, string cur_airport){
    if(cur_depth == max_depth){
        return true;
    }
    
    for(auto &[name, count] : edges[cur_airport]){
        if(count == 0) continue;
        edges[cur_airport][name]--;
        result[cur_depth + 1] = name;
        
        bool hasAnswer = DFS(cur_depth+1, name);
        if(hasAnswer) return true;
        
        edges[cur_airport][name]++;
    }
    return false;
}
 
vector<string> solution(vector<vector<string>> tickets) {
    max_depth = (int) tickets.size();
    for(vector<string> ticket : tickets){
        string src = ticket[0], dest = ticket[1];
        edges[src][dest]++; 
    }
    
    
    
    result.resize(max_depth + 1);
    result[0] = "ICN";
    
    DFS(0, "ICN");
    
    return result;
}

 

시간복잡도

 ticket size를 n이라 하면, edge에 넣는 데 O(loglogn), 꺼내는 데도 O(loglogn)이다. 어떤 출발지로부터 도착지 목록을 가져오는 데는 O(logn)이 걸리고, 이를 순회하는 데 O(nlogn)이 걸린다.

 DFS 자체는, vertex가 O(n)이므로 O(n)이다. 따라서 O(nlogn).

 

후기

 참고로 예전에 풀었던 코드는 다음과 같다. 각 DFS에서 모든 ticket을 보기 때문에 시간이 너무 오래 걸릴 것이다! input이 작아 해결되지만 input이 큰 경우는 해결되지 않을 것. 그리고 코드 자체도 훨씬 간단하다.

vector<string> answer;
 
bool cmp(vector<string> &a, vector<string>&b){
    for(int i = 0; i<a.size(); i++){
        if(a[i] < b[i]) return true;
        else if(a[i] > b[i]) return false;
        else continue;
    }
}
 
void DFS(int depth, int max_depth, string dep, vector<bool>& visited, vector<vector<string>>& tickets, vector<string>& result){
    if(depth == max_depth){
        if(answer.empty()) answer = result;
        answer = cmp(answer, result)? answer : result;
        return;
    }
    
    for(int i = 0; i<max_depth; i++){
        if(tickets[i][0] == dep && !visited[i]){
            visited[i] = true;
            result[depth + 1] = tickets[i][1];  
            DFS(depth+1, max_depth, tickets[i][1], visited, tickets, result);
            visited[i] = false;
        }
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    int size = tickets.size();
    vector<string> result(size + 1); result[0] = "ICN";
    vector<bool> visited(size, false);
    DFS(0, tickets.size(), "ICN", visited, tickets, result);
    return answer;
}