[LeetCode 457] Circular Array Loop

457. Circular Array Loop

주어진 방향 그래프에서 사이클을 찾는 문제이다. 이때, 방향은 음수 또는 양수인데 사이클을 이루는 각 요소들의 방향은 같아야한다.

📌 사이클 탐지 기법

• 대표적인 사이클 탐지 방법에는 아래의 방법이 존재한다.

  1. DFS
  2. Two Pointer (방향 그래프, Floyd's Cycle Detection)
  3. Union-find (무방향 그래프)

• 이 문제에서는 방향 그래프로 주어졌기에, DFS와 Two Pointer를 사용해서 풀이를 작성해 보았다.

📌 접근 방식 (DFS)

• 사실 사이클 디텍션이라고 하면, DFS를 사용한 back edge탐지 방법을 가장 먼저 떠올렸고, 풀이를 작성했다.
• 하지만, 맨 처음 풀이는 시간 초과를 맞았는데.. 이건 알고리즘의 문제가 아니라 디버깅 용으로 작성한 출력함수를 제거하지 않고 제출해서 발생한 문제였다....
• 뭐에 씌였는지, 코드를 싹 지우고 아래 Two Pointer를 사용한 풀이로 수정했고 다시 생각해보니 DFS와 시간 복잡도 차이가 나지 않는다는 생각이 들었고, 재작성 해서 AC를 받았다.

아이디어

• 방향 유지: 한 번에 양수 혹은 음수로만 이동해야 하므로, 재귀 호출 시 시작점의 이동 방향과 다른 경우에는 바로 종료
• 사이클 체크: 방문한 노드를 추적하여, 이미 방문한 노드에 다시 도달할 경우 (단, 사이클의 길이가 1이 아닌 경우) 사이클이 존재하는 것이다.
• 시간복잡도: O(N^2) , 1 <= N <= 5000

📌 정답 (DFS)

class Solution {
public:
    int size;
    bool isCycle = false;
    
    void dfs(int now, int depth, vector<int>& nums, vector<bool>& visited, bool dir) {
        if (visited[now]) {
            if (depth > 1) isCycle = true; 
            return;
        }
        
        visited[now] = true;
        int step = nums[now];
        
        if ((step > 0) != dir) return;
        
        int next = (now + step) % size;
        if (next < 0) next += size; 
        
        // 자기 자신으로 돌아오는 경우는 사이클이 아님
        if(now == next) return;
        
        dfs(next, depth + 1, nums, visited, dir);
    }
    
    bool circularArrayLoop(vector<int>& nums) {
        size = nums.size();
        
        for (int i = 0; i < size; i++) {
            vector<bool> visited(size, false);
            dfs(i, 0, nums, visited, nums[i] > 0);
            if (isCycle) return true; 
        }
        
        return false;
    }
};

📌 접근 방식 (Two Pointer)

• 방향 그래프에서 사이클을 탐지하는 방법에는 Two Pointer를 사용한 Floyd's Cycle Detection도 존재한다.
• 핵심 아이디어는 포인터 두 개를 사용해서, 더 빠르게 순회하는 포인터와 순차적으로 순회하는 포인터가 만나게 된다면 Cycle이 존재한다는 것이다.
  • 증명은 추후 Cycle을 깊게 다루면서 작성해보려고 한다.

아이디어

• Floyd’s Cycle Detection: 느린 포인터와 빠른 포인터를 이용하여 사이클을 찾는다.
• 방향 일치 확인: 각 이동마다 두 포인터가 같은 방향(양수 혹은 음수)으로 움직이는지 확인.
• 자기 자신 이동 제외: 한 칸만 이동하는 경우는 사이클로 치지 않도록 한다.
• 시간복잡도: O(N^2) , 1 <= N <= 5000

📌 정답 (Two Pointer)

class Solution {
public:
    int next(vector<int>& nums, int now) {
        int value = now + nums[now];
        if (value < 0) value += nums.size();
        return value % nums.size();
    }
    
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            int slow = i;
            int fast = next(nums, i);
            
            // 한 칸 이동하는 경우는 사이클 조건(k>1)에 위배
            if (slow == fast) continue;
            
            while (true) {
                if ((nums[slow] > 0) != (nums[fast] > 0)) break;
                
                if (slow == fast) return true;
                
                int nSlow = next(nums, slow);
                int nNext = next(nums, fast);
                int nFast = next(nums, nNext);
                
              
                if ((nums[nNext] > 0) != (nums[nFast] > 0) || nNext == nFast) break;
                if ((nums[slow] > 0) != (nums[nSlow] > 0) || (nums[fast] > 0) != (nums[nFast] > 0)) break;
                
                slow = nSlow;
                fast = nFast;
            }
        }
       
        return false;
    }
};