[Algorithm] Floyd's Cycle Detection이란? (feat. Linked List)

안녕하세요 Foma 입니다!

 

요새 LeetCode에서 Linked List의 사이클에 관련된 문제를 푸는데 slow, fast 포인터를 많이 이용하더라구요.

 

해당 풀이가 이해가 안돼서 찾아 보니 관련된 알고리즘이 있었고, 그것이 Floyd's Cycle Detection 이었습니다.

 

그래서 오늘은 링크드 리스트에서 사이클이 있는지 없는지를 확인할 수 있고, 해당 사이클의 시작점이 어디인지 알아낼 수 있는 Floyd's Cycle Detection 에 대해서 알아보려고 합니다.

 

바로 시작할게요~

---

Floyd's Cycle Detection 이란? 🔁

 

Robert W. Floyd가 고안한 리스트의 사이클을 빠르고 적은 메모리로 찾는 알고리즘입니다.

 

(Robert W. Floyd는 플로이드 와샬 알고리즘을 만들어낸 사람과 동일 인물입니다.)

 

 

거북이와 토끼 (Tortoise and Hare) 알고리즘으로도 많이 알려져 있습니다.

 

왜 거북이와 토끼 알고리즘일까? 🤔

 

바로 거북이처럼 느리게 움직이는 포인터와 토끼처럼 빠르게 움직이는 포인터 이렇게 총 두 포인터가 필요하기 때문입니다.

---

Example

 

아래와 같이 사이클이 있는 링크드 리스트가 있다고 가정하겠습니다.

 

그 다음 사이클이 시작되는 지점을 찾아 보겠습니다.

 

 

0 1 2 3 4 5 6 7 8 3 4 5 6 7 8 ... 으로 3부터 8까지 사이클이 존재하는 리스트입니다.

 

1. 가장 처음 거북이와 토끼가 만나는 지점을 구한다.

 

먼저 거북이(느리게 이동하는 포인터)와 토끼(빠르게 이동하는 포인터)를 가장 첫 번째(head)에 위치합니다.

 

 

 

거북이는 한 칸씩 토끼는 두 칸씩 이동하면 아래와 같이 진행됩니다.

 

그리고 서로 만나게 되는 지점은 6이 되죠.

 

(만약 토끼와 거북이가 만나는 지점이 없다면 사이클이 없다는 의미입니다.)

 

 

2. 거북이를 첫 번째 지점으로 되돌리고, 토끼와 거북이 둘 다 한 칸씩 이동하며 다시 만나는 지점을 구한다.

 

이제 거북이를 가장 첫 번째로 다시 되돌립니다.

 

그 다음부터는 토끼도 거북이와 같이 한 칸씩만 이동할 수 있습니다.

 

이런 식으로 이동하면 토끼와 거북이 서로 만나는 지점은 3이 됩니다.

 

이것은 사이클이 시작되는 지점이 되는 것이죠.

 

---

Proof

 

X: 시작점부터 사이클이 발생하기 전까지 길이

Y: 사이클 시작점부터 첫 번째 만나는 지점 전까지 길이

Z: 첫 번째 만나는 지점부터 사이클 시작점 전까지 길이

C: 사이클의 길이

M: 만나는 지점

 

두 칸씩 이동할 경우 첫 번째 만나는 지점까지 이동할 거리를 계산하면 아래와 같습니다.

 

사이클이 시작되기 전 X만큼 이동하고 사이클을 r₁바퀴 돌고 Y만큼 이동해 M지점에서 거북이를 만나게 됩니다.

 

h = x + r₁c + y

 

한 칸씩 이동할 경우 첫 번째 만나는 지점까지 이동할 거리를 계산하면 아래와 같습니다.

 

사이클이 시작되기 전 X만큼 이동하고 사이클을 r₂바퀴 돌고 Y만큼 이동해 M지점에서 토끼를 만나게 됩니다.

 

t = x + r₂c + y

 

토끼는 두 칸씩, 거북이는 한 칸씩 움직이므로 다른 식으론 아래와 같이 쓸 수 있습니다.

 

2T = H

 

즉, 아래와 같이 풀어 쓸 수 있죠.

 

2(x + r₂c + y) = x + r₁c + y 
-> 2x + 2r₂c + 2y = x + r₁c + y
-> 2x + 2y - x - y = r₁c - 2r₂c
-> x + y =  (r₁ - 2r₂)c
-> x = (r₁ - 2r₂)c - Y
-> x = (r₁ - 2r₂ - 1)c + c -y

 

이 때 r₁ - 2r₂ - 1은 상수이므로 r₃라는 새로운 상수를 만들어 대체시켜 줍니다.

 

x = r₃c + c - y

 

c는 사이클이므로 다른 말로 y + z가 될 수 있습니다.

 

x = r₃c  + y + z - y
-> x = r₃c  + z

 

즉, 시작점부터 사이클이 시작되기 전까지의 길이는(x) 사이클을 r₃만큼 돌고 만난 지점부터 사이클이 시작점까지의 길이(z)와 같다가 성립됩니다.

 

고로 첫 번째로 만난 지점부터 시작점까지 차례로 한 칸씩 이동하면 사이클의 시작점을 알 수 있게 되는 것이죠.

---

Code

 

아래와 같이 파라미터로 ListNode를 받고, 사이클의 시작인 ListNode를 반환하는 코드를 작성해 보겠습니다.

 

func floydCycleDetection(_ head:ListNode?) -> ListNode? {

 

먼저 한 칸씩 움직일 거북이(tortoise)와 두 칸씩 움직일 토끼(hare)를 가장 처음 노드인 head로 설정해 줍니다.

 

    var tortoise = head
    var hare = head

 

while문을 이용해 tortoise는 next로 한 칸씩, hare는 next?.next로 두 칸씩 이동해 줍니다.

 

만약 tortorise와 hare가 같다면 while문을 멈춰 줍니다.

 

    while true {
        tortoise = tortoise?.next
        hare = hare?.next?.next
        if tortoise === hare {
            break
        }
    }

 

거북이를 다시 처음으로 되돌려 줍니다.

 

    tortoise = head

 

이번엔 tortoise와 hare 둘 다 똑같이 next로 한 칸씩만 이동시켜 줍니다.

 

만약 tortorise와 hare가 같다면 while문을 멈춰 줍니다.

 

    while true {
        tortoise = tortoise?.next
        hare = hare?.next
        if tortoise === hare {
            break
        }
    }

 

 

tortoise 또는 hare를 반환해 주면 사이클의 시작점(3)이 반환됩니다.

 

 

    return tortoise //value: 3

---

Reference

 

• https://www.youtube.com/watch?v=PvrxZaH_eZ4&t=21s 
• https://en.wikipedia.org/wiki/Cycle_detection