LeetCode (C/C++) 565. Array Nesting

https://leetcode.com/problems/array-nesting/description/

 

 

---

풀이

현재 지점에 방문하지 않았더라면 해당 지점을 방문해서 사이클 내의 노드 수를 찾는다.

같은 사이클 내의 지점들은 모두 같은 수의 노드를 방문하고 사이클이 종료되므로 방문 처리 후 최대 노드 수를 갱신한다.

---

코드

class Solution {
public:
    bool visited[1'000'000];
    int dfs(vector<int>& nums, int now, int nowDepth) {

        // 현재 지점이 방문했던 곳이라면 현재 깊이 반환
        if (visited[now])
            return nowDepth;

        visited[now] = true;
        return dfs(nums, nums[now], nowDepth + 1);
    }

    int arrayNesting(vector<int>& nums) {
        int maxLen = 1;
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];

            // 방문하지 않았다면 깊이 체크
            if (!visited[num])
                maxLen = max(maxLen, dfs(nums, num, 1) - 1);
        }
        return maxLen;
    }
};