
[LeetCode] Longest Cycle in a Graph
·
알고리즘/LeetCode
문제https://leetcode.com/problems/longest-cycle-in-a-graph/난이도: Hard토픽: DFS, Graph, Topological sorting그래프가 주어지면 그래프 내의 사이클중 제일 길이가 긴 사이클 길이를 구하는 문제이다. 접근방법그래프에서 사이클을 감지하는 가장 간단한 알고리즘으로 Floyd의 거북이 & 토끼 알고리즘이 있다. Floyd의 거북이 & 토끼 알고리즘거북이와 토끼를 시작점에 놓고 거북이는 한 번에 1칸 움직이고, 토끼는 한 번에 2칸 움직인다.그래프에 사이클이 있다면 토끼와 거북이는 어느 한 지점에서 반드시 만나게 된다.사이클을 감지하는 건 알겠는데, 어떻게 하면 사이클의 길이를 측정할 수 있을까?위의 그래프에서 거북이와 토끼는 4번 이동하여 노..