[LeetCode] 457. Circular Array Loop

😎풀이

1. nums를 순회하며, 각 노드를 시작점으로 순환이 일어나는 노드인지 검사
   1-1. 만약 두 개 이상의 노드를 거쳐 시작점으로 돌아왔다면, 순환 발생
   1-2. 만약, 모든 노드의 방향이 동일하지 않다면, 순환 미발생
   1-3. 시작점으로 돌아오지 않고 중간 무한 순회를 한다면, 순환 미발생
2. 순환이 일어나는 노드가 있다면 true를 반환하고, 그렇지 않다면 false 반환

function circularArrayLoop(nums: number[]): boolean {
    const n = nums.length
    function dfs(i: number, originIdx: number, visited: Set<number>) {
        if(i === originIdx && visited.size >= 2) return true
        if(Math.sign(nums[i]) !== Math.sign(nums[originIdx])) return false
        if(visited.has(i)) return false
        visited.add(i)
        const curStep = nums[i]
        let nextIdx = (i + nums[i]) % n
        if(nextIdx < 0) nextIdx += n
        return dfs(nextIdx, originIdx, visited)
    }
    for(let i = 0; i < n; i++) {
        const isCircular = dfs(i, i, new Set<number>())
        if(isCircular) return true
    }
    return false
};