Daily LeetCode Challenge - 2360. Longest Cycle in a Graph

Problem From.

https://leetcode.com/problems/longest-cycle-in-a-graph/

오늘 문제는 그래프가 주어졌을때, 그 안에서 순환하는 사이클 중 가장 큰 사이클의 크기를 구하는 문제였다.

이 문제는 DFS 를 통해서 풀 수 있었는데, 각 노드를 탐색하면서 각 노드에서 다른 노드로 갈 때마다 path 를 기록해둔다. 그리고 다시 다른 노드를 탐색할때 path 에 이전에 탐색했던 노드가 있는지 본 뒤에 있다면 사이클이 만들어진 것이므로 그 값 -1 을 저장해둔다.

마지막으로 저장되어있는 값들 중에서 가장 큰 값을 리턴하면 된다.

class Solution {
    fun longestCycle(edges: IntArray): Int {
        var result = -1
        var visited = mutableMapOf<Int, Int>()
        for (i in 0 until edges.size) {
            result = Math.max(result, traversal(edges, i, 0, visited, mutableSetOf()))
        }

        return result
    }

    private fun traversal(
        edges: IntArray,
        node: Int,
        steps: Int,
        visited: MutableMap<Int, Int>,
        path: MutableSet<Int>
    ): Int {
        if (node == -1) return -1
        if (visited.containsKey(node)) {
            return if (path.contains(node))
                steps - visited[node]!!
            else -1
        }
        
        visited[node] = steps
        path.add(node)

        return traversal(edges, edges[node], steps + 1, visited, path)
    }
}