[C/C++] 연결 리스트(Linked List)의 순환 구조 찾기, 토끼와 거북이

이번 포스팅에서 알아볼 것은 연결 리스트(linked list)의 순환 구조 찾기입니다. 이를 알아보기 위해선 먼저 연결 리스트의 간단한 형태에 대해 정의하고자 합니다.

struct LinkedList
{
	struct LinkedList* next;
	int item;
};

struct LinkedList* new_linked_list(int item)
{
	struct LinkedList* res = new LinkedList;
	res->next = NULL;
	res->item = item;
	return res;
}

연결 리스트의 구조는 위와 같이 자기 자신의 포인터를 포함한 구조체입니다. 가장 먼저 선언된 구조체가 머리(head)라고 불리며, 이후에 생성되는 구조체들은 이전에 나온 연결 리스트의 next가 가리키는 형태로 되어 있습니다. 다음 item이라는 멤버 변수는 연결 리스트가 담고자 하는 형태의 자료형이며, 이번 포스팅에서는 단순한 예시를 위해 정수형으로 선언하였습니다.

다음은 연결 리스트의 생성자를 단순하게 사용하기 위해 함수로 만든 것입니다. new_linked_list()는 연결 리스트가 사용하고자 하는 자료형(여기선 정수형)을 입력으로 받고 있습니다. 함수 내부를 간단히 살펴보면, 먼저 이 함수의 목적인 연결 리스트의 한 요소를 생성하기 위한 res변수를 연결 리스트의 포인터로 선언한 뒤 동적 할당을 통해 정의해줍니다. 다음은 해당 연결 리스트의 멤버 변수인 next와 item을 각각 NULL과 입력 파라미터 item을 대입해줍니다. 최종적으론 res변수는 함수의 출력으로 나가게 됩니다.

이제 본격적으로 시작하기 앞서 연결 리스트의 순환 구조 형태에 대해 간단히 알아보고자 합니다.

연결 리스트의 순환 구조(발퀄)

위의 그림에서 보다시피 각 사각형들은 모두 LinkedList를 나타내는 도식들입니다. 따라서 위 코드 상황에 대입해 보면, 연결 리스트 1의 next는 연결 리스트 2이고, 연결 리스트 2의 next는 연결 리스트 4입니다. 이러한 방식으로 첫번재 연결 리스트부터 5번째 연결 리스트는 각자의 다음 연결 리스트와 연결된 상태입니다. 여기서 눈여겨봐야 하는 부분은 바로 어떤 연결 리스트부터 시작하더라도 결국 2 -> 4 -> 3 -> 2.. 를 반복하며 순환하는 형태로 구성되어 있다는 점입니다.

그렇다면 어떻게 하면 이러한 순환 구조를 파악할 수 있는지 아이디어를 구상해보면, 가장 먼저 생각 든 생각은 각 연결 리스트의 구조체에 flag변수를 추가하여 한번 확인된 연결 리스트를 표시하는 방법이 있습니다. 이렇게 되면 어떤 연결 리스트에 방문할 때, flag를 확인하여 두 번째로 방문하게 된 연결 리스트인지 알 수 있고, 그때 이것이 연결 리스트라는 것을 알려주면 됩니다.

하지만 이러한 방법의 문제점이라고 한다면, 주어진 연결 구조체를 변형할 수 없는 상황에서는 이를 적용하기 어렵다는 점입니다. 이를 해결하기 위해 flag의 역할을 해주는 것을 외부 구조체에서 만들어 사용할 수 있습니다. 일종의 해시 테이블(hash table)을 활용하는 방법입니다.

typedef long long address_t;

bool IsLoopHashTable(struct LinkedList* head)
{
	std::map<address_t, bool> inspect_map;
	struct LinkedList* curr = head;

	while (curr != NULL)
	{
		std::map<address_t, bool>::iterator fmap = inspect_map.find((address_t)(curr));
		if (fmap == inspect_map.end())
		{
			inspect_map.insert({ (address_t)(curr), true });
		}
		else
		{
			return true;
		}
		curr = curr->next;
	}

	return false;
}

IsLoopHashTable() 함수를 만들었습니다. 이 함수는 연결 리스트의 머리를 입력으로 받아 순환 구조이면 true를 출력하고, 아니면 false를 출력하도록 한 함수입니다. 한 줄씩 살펴본다면 먼저 해시 테이블 구조체인 std::map<address_t, bool> inspect_map을 선언해줍니다. 이 변수는 이후 각 연결 리스트를 검사하면서 해당 연결 리스트의 주소가 처음 발견된 것인지 아닌지를 확인하기 위한 것입니다.

다음으로 반복문(while)을 통해 연결 리스트의 각 요소를 하나씩 검사하는 부분입니다. 먼저 while문의 조건은 연결 리스트의 한 요소가 NULL이 아니면 계속 반복하도록 되어 있습니다. 이것은 위에서 연결 리스트 생성할 때, 초기값으로 next는 NULL 값이기 때문에 만약 반복 중에 NULL이 나오게 된다면 종료하라는 의미입니다. 다음 curr변수의 주소 값이 거쳐간 요소인지 확인하는 부분입니다. curr변수는 포인터 변수이므로, 변수 앞에 *가 없다면 그 변수가 가리키는 주소 값을 의미하게 됩니다. 이때, 해당 주소를 일종의 구분자(ID)로 활용하기 위해 address_t(typedef long long address_t)로 변환하여 inspect_map에 저장되었는지를 확인합니다. 이때 inspect_map에 없는 값이라면 새롭게 추가해주고, 있는 값이라면 순환 연결 리스트라는 의미이기 때문에 true를 반환해줍니다. 반환되지 않았다면 curr변수에 curr->next를 대입하여 다음 연결 리스트를 검사하도록 합니다.

반복문이 종료된다면 해당 연결 리스트에는 순환 구조가 없다는 의미이기 때문에 false를 출력해 줍니다.

가장 기본이 되는 아이디어로부터 출발한 이 방법에는 사소한 단점 하나가 있다고 생각이 드는데, 이는 연결 리스트의 크기가 매우 크다면 해시 테이블의 크기가 점점 증가해야만 한다는 것이다. 물론 해시 테이블은 원하는 요소를 찾아내는 데에는 O(1)만큼의 시간이 소요되기 때문에 큰 문제는 없을 것이다. 다만, 메모리 관점에서 본다면 N개의 연결 리스트 요소가 있다고 한다면 O(N)의 크기로 메모리가 사용되어야 하기 때문에 까다로운 환경에서는 어려울 수도 있어 보인다(물론 요즘 그런 환경은 매우 적다.)

다음으로 알아볼 것은 이 포스팅을 하게 만든 장본인인 '토끼와 거북이'이다. 플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise and Hare Algorithm)으로 아주 간단한 아이디어로 작성되었다. 연결 리스트의 한 지점에서 시작하여 발이 느린 거북이는 한 칸씩(slow = slow->next), 발이 빠른 토끼는 두 칸씩(fast = fast->next->next) 움직이게 된다. 왜 이렇게 만날 수밖에 없는지는 수학적으로 증명되었지만, 다른 블로그를 참고해 보는 것이 더 좋을 것 같다 [*][**]. 

bool IsLoopRabbitTurtle(struct LinkedList* head)
{
	struct LinkedList* fast = head;
	struct LinkedList* slow = head;

	while (slow && fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast)
		{
			return true;
		}
	}
	return false;
}​

핵심 아이디어는 위에서 모두 설명하였으니, 간단한 코드의 구조만 살펴보자. 위의 코드와 차이가 나는 부분만 본다면 반복문의 조건이 조금 더 까다로워졌다. 이전에는 curr만 NULL이 아니면 되었는데, 이젠 slow, fast, 그리고 fast->next까지 NULL이 아니어야 한다. 이는 slow와 fast 두 개의 연결 리스트 요소를 사용하기 때문에 앞에 두 변수가 추가된 것이고, fast->next는 토끼가 두 칸씩 움직여야 하기 때문에 추가되었다. 그 외 나머지는 위에서 설명한 내용과 동일합니다.

이제 위에서 작성한 두 개의 함수를 이용해 4가지의 테스트 케이스를 만들어 확인합니다. 먼저 테스트 케이스 1과 2는 가장 단순한 형태의 연결 리스트입니다. 테스트 케이스 1번은 0번부터 9번까지 순차적으로 연결된 다음, 9번이 0으로 연결되는 순환 연결 리스트이고, 테스트 케이스 2번은 0번부터 9번까지만 순차적으로 연결된 순환하지 않는 연결 리스트입니다. 테스트 케이스 3번과 4번은 모양이 조금 복잡한데, 아래의 그림과 같은 형태로 만들어져 있습니다.

복잡한 연결 리스트

이런 4가지 형태의 테스트 케이스를 코드로 만들면 아래와 같이 만들 수 있습니다.

struct LinkedList* create_test_case_1(void)
{
	struct LinkedList* head = new_linked_list(0);
	struct LinkedList* curr = head;
	for (int i = 1; i < 10; i++)
	{
		curr->next = new_linked_list(i);
		curr = curr->next;
	}
	curr->next = head;
	return head;
}

//Is Non-Loop
struct LinkedList* create_test_case_2(void)
{
	struct LinkedList* head = new_linked_list(0);
	struct LinkedList* curr = head;
	for (int i = 1; i < 10; i++)
	{
		curr->next = new_linked_list(i);
		curr = curr->next;
	}
	return head;
}

// Complext Case (Loop)
struct LinkedList* create_test_case_3(void)
{
	struct LinkedList* lists[10];
	for (int i = 0; i < 10; i++)
	{
		lists[i] = new_linked_list(i);
	}
	lists[0]->next = lists[9];
	lists[1]->next = lists[2];
	lists[2]->next = lists[9];
	lists[3]->next = lists[2];
	lists[4]->next = lists[6];
	lists[5]->next = lists[2];
	lists[6]->next = lists[7];
	lists[7]->next = lists[5];
	lists[8]->next = lists[4];
	lists[9]->next = lists[4];

	return lists[4];
}

// Complext Case (Non-Loop)
struct LinkedList* create_test_case_4(void)
{
	struct LinkedList* lists[10];
	for (int i = 0; i < 10; i++)
	{
		lists[i] = new_linked_list(i);
	}
	lists[0]->next = lists[9];
	lists[1]->next = lists[2];
	lists[2]->next = lists[9];
	lists[3]->next = lists[2];
	lists[4]->next = NULL;
	lists[5]->next = lists[2];
	lists[6]->next = lists[7];
	lists[7]->next = lists[5];
	lists[8]->next = lists[4];
	lists[9]->next = lists[4];

	return lists[9];
}

각각의 테스트 케이스를 실행시켜 main 함수에서 확인하는 코드와 결과는 아래 코드에서 확인해볼 수 있습니다.

int main(void)
{
	struct LinkedList* test_case_1 = create_test_case_1();
	struct LinkedList* test_case_2 = create_test_case_2();
	struct LinkedList* test_case_3 = create_test_case_3();
	struct LinkedList* test_case_4 = create_test_case_4();

	std::cout << "\nHash Table Algorithm\n";
	std::cout << "Test Case 1(Circular Loop)    : " << (IsLoopHashTable(test_case_1) ? "true" : "false") << "\n";
	std::cout << "Test Case 2(Non-Circular Loop): " << (IsLoopHashTable(test_case_2) ? "true" : "false") << "\n";
	std::cout << "Test Case 3(Complex Loop)     : " << (IsLoopHashTable(test_case_3) ? "true" : "false") << "\n";
	std::cout << "Test Case 4(Complex Non-Loop) : " << (IsLoopHashTable(test_case_4) ? "true" : "false") << "\n";

	std::cout << "\nRabbit and Turtle Algorithm\n";
	std::cout << "Test Case 1(Circular Loop)    : " << (IsLoopRabbitTurtle(test_case_1) ? "true" : "false") << "\n";
	std::cout << "Test Case 2(Non-Circular Loop): " << (IsLoopRabbitTurtle(test_case_2) ? "true" : "false") << "\n";
	std::cout << "Test Case 3(Complex Loop)     : " << (IsLoopRabbitTurtle(test_case_3) ? "true" : "false") << "\n";
	std::cout << "Test Case 4(Complex Non-Loop) : " << (IsLoopRabbitTurtle(test_case_4) ? "true" : "false") << "\n";

	return 0;
}​

Hash Table Algorithm
Test Case 1(Circular Loop)    : true
Test Case 2(Non-Circular Loop): false
Test Case 3(Complex Loop)     : true
Test Case 4(Complex Non-Loop) : false

Rabbit and Turtle Algorithm
Test Case 1(Circular Loop)    : true
Test Case 2(Non-Circular Loop): false
Test Case 3(Complex Loop)     : true
Test Case 4(Complex Non-Loop) : false

D:\Sangwons_Room\02_개인문서\스터디\BeakJoon\x64\Debug\beakjoon.exe(프로세스 31904개)이(가) 종료되었습니다(코드: 0개).
디버깅이 중지될 때 콘솔을 자동으로 닫으려면 [도구] -> [옵션] -> [디버깅] > [디버깅이 중지되면 자동으로 콘솔 닫기]를 사용하도록 설정합니다.
이 창을 닫으려면 아무 키나 누르세요...

 

참조

• [*] https://en.wikipedia.org/wiki/Cycle_detection
• [**] https://fierycoding.tistory.com/45