NeuroWhAI의 잡블로그

플로이드 순환 찾기 알고리즘(Floyd's cycle-finding algorithm) 설명 본문

개발 및 공부/알고리즘

플로이드 순환 찾기 알고리즘(Floyd's cycle-finding algorithm) 설명

NeuroWhAI 2020. 2. 28. 21:53


이 알고리즘은 우연히 알게되었다.
구현은 참으로 간단한데 이게 왜 되는지 이해가 안돼서 한참을 삽질했다.
정리할 겸 글을 적어본다.

 

일단 알고리즘의 목적은 유향 그래프든 연결 리스트든 그 속에 순환이 존재하는지, 존재한다면 그 시작 지점은 어딘지 찾는 것이다.
1. 먼저 시작 노드를 가리키는 포인터 2개를 준비한다.
2. 노드의 간선을 따라 포인터를 이동시킬 것인데 하나는 1칸씩, 다른 하나는 2칸씩 옮긴다.
3. 순환이 없다면 두 포인터가 만나는 일은 없겠지만 순환이 존재하면 결국 만나게 된다.
4. 이때 느린 포인터를 다시 시작 노드로 옮기고 이번엔 둘 다 1칸씩 이동시킨다.
5. 그럼 또 결국 어떤 지점에서 만나게 되는데 놀랍게도 여기가 순환이 시작되는 곳이다.

 

이 방법으로 순환을 찾을 수 있다는 것은 직관적으로 이해가 가능한데 어떻게 느린 포인터를 시작 지점으로 옮겨 다시 진행시키는 것 만으로 순환의 시작 지점을 찾을 수 있는진 이해가 안되었다.
증명을 통한 납득을 위해선 수학이 필요하다.

https://cs.stackexchange.com/a/45540/116303

여기 예시가 있다.
순환의 길이를 L로 두자.
L = y + z
위 4번 단계에서 두 포인터가 순환의 시작점에서 만나기 위해선 아래 조건을 만족해야 한다.
z = x mod L
위 그림만 보면 z = x로 하면 될 것 같지만 x가 z와 달라도 순환을 몇 바퀴 돈 후 만날 수도 있으니 이렇게 식을 세운다.
느린 포인터가 meeting-point까지 진행하는 거리를 M으로 두자.
M = x + y
빠른 포인터는 2배의 속도로 가니까 만났을 때 2M만큼 이동했을 것이다.
2M을 다르게 표현하려면 아래와 같이 할 수 있다.
2M = M + kL (k는 아래에서 설명.)
왜?
M + kL을 보자.
느린 포인터는 M만큼 움직였고 M 위치에 있다.
빠른 포인터도 만나긴 했으니 M 위치에 있는 것은 같다.
하지만 실제론 순환을 1바퀴 이상 돈 후 그 위치에 있게 된 것이다. (순환을 돌지 않았으면 애초에 만날 수가 없음.)
여기서 돈 바퀴 수를 k로 하면 느린 포인터보다 kL 만큼 더 간 후 M 위치에 있게 되었다는 것으로 표현할 수 있다.
때문에 2M = M + kL이 된다.
식을 정리하면 아래와 같이 된다.
2M = M + kL
M = kL
x + y = kL
x = kL - y
이 식을 4번 단계에서 느린 포인터가 x만큼 움직일 동안 kL - y만큼 움직일 빠른 포인터 입장에서 생각해보자.
kL - y라는 것은 순환을 k바퀴 돈 거리에서 y만큼 덜 간 거리라는 것이다.
위 그림에서 meeting-point에 있을 빠른 포인터를 kL - y만큼 움직인 후의 위치는 결국 z만큼 움직인 위치와 동일하게 된다.
즉, 순환의 시작 지점에 있게 된다.
시작 노드에서 x만큼 이동한 느린 포인터도 해당 지점에 있게 되므로 여기서 만나게 되며 만난 그 장소가 바로 순환의 시작 지점일 수 밖에 없다.

 

이 알고리즘의 다른 이름은 Floyd's Tortoise and Hare인데 느린 포인터가 거북이고 빠른 포인터가 토끼인 것이다.
시작 노드에서 달리기 경주를 하는 것 처럼 보여서 그런지 이런 이름이 있는 것 같다.



Comments