23.03.26. 풀었던 문제들

Leetcode 2360. Longest Cycle in a Graph

 directed graph에서 cycle을 찾는 문제이다. 예전에 소마 코테였나? cycle을 찾는 문제를 DFS로 푼 적이 있었다. 그것처럼 풀면 될 것 같았다. 로직은 아래와 같다.

• DFS를 한다.
  • visited하지 않은 vertex를 찾으면 일반적인 DFS를 수행한다. 이 때, 방문 기록을 따로 기록한다. - 1번
  • visited한 vertex를 찾으면 탐색을 종료하고, 지금까지 방문 기록에서 해당 vertex를 찾는다. 만약 있다면 cycle이 있는 것이다. 없다면 cycle이 없는 것이다. - 2번

 이렇게 생각할 수 있는 이유는 directed graph이고, 모든 vertex에서 edge가 최대 1개이기 때문이다. 만약 어떤 cycle이 있다면 2번 로직에 의해 cycle이 끝날 때까지 탐색한다. 따라서 다른 탐색으로 인해 cycle이 더 커질 염려를 하지 않아도 된다.

// Runtime 294 ms Beats 56.14%
// Memory 139.1 MB Beats 48.90%

class Solution {
public:
    vector<int> edges;
    vector<bool> visited;
    int answer = 0;
    void DFS(int v, vector<int>& log){ // 일반적 DFS에 방문 기록을 추가
        int w = edges[v];
        if(w == -1) return;
        if(!visited[w]){ // 1번. not visited, then keep traverse
            log.push_back(w);
            visited[w] = true;
            DFS(w, log);
        }
        else{ // 2번. if visited, then stop traverse, find w in traverse log
            int cycleidx = log.size();
            for(int i = 0; i<log.size(); i++){
                if(log[i] == w){
                    cycleidx = i;
                    break;
                }
            }
            answer = max(answer, (int)log.size() - cycleidx);
            return;
        }
    }
    
    int longestCycle(vector<int>& E) {
        edges = E;
        visited.resize(E.size());
        fill(visited.begin(), visited.end(), false);

        for(int i = 0; i<edges.size(); i++){
            if(!visited[i]){
                visited[i] = true;
                vector<int> log = {i};
                DFS(i, log);
            }
        }
        return answer == 0 ? -1 : answer;
    }
};

 

시간복잡도

 DFS이므로 O(V + E). E = V이므로 O(V). 그리고 DFS가 끝날 때 방문했던 vertex의 for문을 한 번 돌린다. 따라서 한 번의 DFS에서 O(2V)를 사용한다. 따라서 O(V)

 

공간복잡도

 worst case 함수 스택을 O(V)만큼 사용하고, edges, visited, log에 O(V)만큼 사용한다. O(V).