[알고리즘/토끼와 거북이] 플로이드의 토끼와 거북이 (Floyd's Tortoise and Hare) 알고리즘

이번 포스팅은 플로이드의 토끼와 거북이 알고리즘입니다.

이 알고리즘은 Linked List에서 사이클이 있는지 확인, 사이클의 시작점, 사이클의 길이를 O(N) 시간복잡도 (공간복잡도는 O(1))로 알아낼 수 있습니다.

개인적으로 색다른 알고리즘이기도, 다양한 알고리즘 문제에서 활용하고 있는 알고리즘으로, 확실히 공부하고 싶은 마음에 올립니다.

 

출처 : https://kimsereylam.com/

위와 같은 사이클이 있는 연결리스트가 있다면 사이클의 시작점은 2, 사이클의 길이는 4입니다.

이를 알아내는 방법은 아래와 같습니다.

 

# 사이클이 있는지 판단

1. 연결리스트의 시작점에 2개의 포인터를 놓습니다. (하나의 포인터는 토끼, 하나는 거북이라 부르겠습니다.)

2. 토끼라는 포인터는 한번 이동할때 2칸씩, 거북이는 한번에 한칸씩 이동합니다.

3. 이를 반복하다가 토끼와 거북이가 만나게 된다면 사이클이 존재하는 것이고, 만약 토끼와 거북이가 만나지 않았고 토끼가 먼저 연결리스트의 끝 지점에 도달한다면 사이클이 없는 것입니다.

 

# 사이클의 시작점 판단

1. 먼저 위의 알고리즘을 수행해서 토끼와 거북이가 만난 지점 x가 있습니다. 초기 위치는 거북이는 연결리스트의 시작점, 토끼는 x 위치입니다.

2. 토끼와 거북이가 만날 때까지 모두 한번에 한칸씩 이동합니다.

3. 토끼와 거북이가 만나는 지점이 생기는데, 그 지점이 사이클의 시작점입니다.

 

# 사이클의 길이 판단

1. 사이클의 시작점에 토끼와 거북이가 모두 존재합니다.

2. 토끼만 한칸씩 이동하면서, 길이를 세줍니다.

3. 토끼가 거북이가 있는 자리에 오게 되면 2번 과정을 멈춥니다. 그때의 길이가 사이클의 길이가 됩니다.

 

# 알고리즘 (java, Kotlin)

문제 링크 : leetcode.com/problems/linked-list-cycle-ii/submissions/

Linked List Cycle II - LeetCode

- JAVA

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        /*
        * 사이클 존재 여부 판단, 토끼는 한번에 두칸씩, 거북이는 한칸씩 이동합니다.
        */
        ListNode tor = head;
        ListNode har = head;
        
        boolean hasCycle = false;
        while(tor != null && har != null && har.next != null) {
            tor = tor.next;
            har = har.next.next;
            
            //토끼와 거북이가 만난다면 사이클이 존재
            if(tor == har) {
                hasCycle = true;
                break;
            }
        }
        
        // 사이클이 없다면 null 반환
        if(!hasCycle) {
            return null;
        }
        
        /*
        * 사이클의 시작점 판단, 거북이를 시작점으로 이동, 모두 한칸씩 이동하다가 만나는 지점이 사이클의 시작점입니다. 
        */
        tor = head;
        
        while(tor != har) {
            tor = tor.next;
            har = har.next;
        }
        //사이클길이 판단
        int len = 0;
        while(tor != har) {
            har = har.next;
            len++;
        }
        
        System.out.println(len);
        
        return tor;
    }
}

- Kotlin

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
 
class Solution {
    fun detectCycle(head: ListNode?): ListNode? {
        var tor : ListNode? = head
        var har : ListNode? = head
        
        var hasCycle = false
 
        while(true) {
            tor = tor?.next ?: break
            har = har?.next?.next ?: break
            
            if(tor == har) {
                hasCycle = true
                break
            }
        }
        
        if(!hasCycle) {
            return null
        }
        
        
        var newTor = head!!
        var newHar = har!!
        
        while(newTor != newHar) {
            newTor = newTor.next
            newHar = newHar.next
        }
        
        return newTor
    }
}

 

 

# 증명

처음 토끼와 거북이가 만나고, 거북이를 처음 지점으로 이동시킨 이후 한칸씩 이동하며 서로 만나는 지점이 사이클의 시작점인 이유를 증명하겠습니다.

출처 :  https://javabypatel.blogspot.com/

처음 시작점에서 시작해서 사이클이 존재하면 토끼와 거북이는 세모로 표시된 지점에서 만날 것입니다.

p (연결리스트 시작점으로부터 사이클 시작점 까지의 길이)
q (연결리스트 시작점 부터 세모지점까지의 길이)
r(세모 지점으로 부터 연결리스트 시작점까지의 길이)

사이클의 판단 여부를 위해 거북이가 움직인 길이 : p + q

토끼는 2칸씩 움직이므로 거북이가 움직인 길이의 2배 : 2(p+q) = 2p+2q

토끼가 실제 움직인 길이 : p + q + r + q 입니다. (거북이를 만나려면 최소 한번은 연결리스트의 사이클을 돌아서 다시 세모지점으로 와야하기 때문입니다.)

즉, 토끼가 움직인 길이는 2p + 2q = p + 2q + r로 정리할 수 있고

식을 정리하면, p = r이 되게 됩니다.

세모지점에서 거북이는 시작점으로 이동, 토끼는 세모지점에서 시작해서 각각 한칸씩 이동하다가 둘이 만나는 지점이 연결리스트의 시작점이 되려면 p = r을 성립해야하므로, 이 알고리즘을 증명할 수 있습니다.

 

 

 

아래의 문제는 이 알고리즘을 적용하기 좋은 문제입니다.

leetcode.com/problems/linked-list-cycle/

Linked List Cycle - LeetCode

leetcode.com/problems/find-the-duplicate-number/

Find the Duplicate Number - LeetCode

 

 

* 참고 : velog.io/@lacomaco/토끼와-거북이-알고리즘-LeetCode-142, medium.com/@tuvo1106/the-tortoise-and-the-hare-floyds-algorithm-87badf5f7d41