Floyd's Cycle Detection Algorithm

전에 어떤 곳에서 듣고 바로 답을 못했던 문제가 있다.

링크드 리스트에서 cycle이 있는지 어떻게 확인하나요?

이 문제는 플로이드의 순환 찾기 알고리즘(Floyd’s Tortoise and Hare이라고 불리기도 한다)을 사용하면 쉽게 해결할 수 있다. 그렇다면 플로이드의 순환 찾기 알고리즘에 대해 좀 더 자세히 알아보도록 하자.

알아보기에 앞서 이 알고리즘의 space complexity는 O(1), time complexity는 O(n)이다.[1]

먼저 1의 속도로 움직이는 포인터와 2의 속도로 움직이는 포인터를 링크드 리스트의 시작점에서 놓고 시작했을 때 두 포인터가 만나면 사이클이 존재한다. 이를 코드로 표현하면 다음과 같다.[2]

int containsLoop(node *head){
  node *slowptr = head, *fastptr = head;
  while(fastptr && fastptr->next){
    slowptr = slowptr->next;
    fastptr = fastptr->next->next;
    if(fastptr == slowptr)
      return 1;
  }
  return 0;
}  

이제 이 사이클의 시작점을 찾는 방법도 같이 알아보자.[3]

간단하게 말하면 두 포인터가 처음 만났을 때 속도가 1인 포인터를 다시 시작점으로 보내고, 두 포인터 모두 속도 1로 움직이면 cycle의 시작 지점에서 두 포인터가 다시 만난다. 이를 수식을 통해 알아보면 다음과 같다.

두 포인터가 가위표 위치에서 처음 만났다고 하면, 속도가 1인 포인터는 x+y만큼을 이동했을 것이고, 속도가 2인 포인터는 x+y+kL만큼 이동했을 것이다. 왜냐하면 속도가 2인 포인터는 사이클을 1바퀴 이상을 돌다가 속도가 1인 포인터와 만나기 때문이다.

이 때 속도가 2인 포인터는 같은 시간동안 속도가 1인 포인터가 움직인 거리의 두배만큼 움직이기 때문에 2(x+y) = x+y+kL이라는 식을 세울 수 있다. 이 수식을 다음과 같은 순서로 정리해볼 수 있다.

2(x+y) = x+y+2kL
x+y = kL
x = kL-y

이 때 속도가 1인 포인터를 시작점으로 놓고 둘다 같은 속도로 움직이면 속도 1 포인터가 x만큼 갔을 때 원래 속도가 2였던 포인터(현재는 속도 1로 움직이고 있음)는 사이클에서 y만큼 덜 간 위치까지 가기 때문에 두 포인터가 cycle이 시작되는 점에서 만날 수 있는 것이다.

이 과정을 코드로 표현하면 다음과 같다.[2]

int findLoopPoint(node *head){
  node *slowptr = head, *fastptr = head;
  int loop = 0;
  while(fastptr && fastptr->next){
    slowptr = slowptr->next;
    fastptr = fastptr->next->next;
    if(fastptr == slowptr){
      loop=1;
      break;
  }
  if(loop){
    slowptr = head;
    while(slowptr != fastptr){
      fastptr = fastptr->next;
      slowptr = slowptr->next;
    }
    return fastptr->data;
  }
  return 0;
}

출처:
[1] medium.com/@nikeshshetty/floyd-cycle-detection-ef2642022578
[2] snutiise.github.io/Floyd’s-Cycle-Detection-Algorithm/
[3] neurowhai.tistory.com/384