[C/C++]달팽이 격자 알고리즘 구현

안녕하세요. VeriLog입니다.

 

오늘은 C++을 이용하여 달팽이 격자 알고리즘을 만들어보려고 합니다.

 

이후에 달팽이 격자에서 임의의 두 지점을 정하고, 두 지점을 꼭지점으로 하는 사각형이 정사각형인지 판단하는 알고리즘을 만들어볼 예정입니다.

 

먼저, NxN 달팽이 격자 알고리즘을 구현해보겠습니다. 5 x 5 달팽이 격자는 아래 사진과 같이 그릴 수 있습니다. 

5x5 달팽이 격자

달팽이 격자 C++로 구현하면 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>

using namespace std;

// 달팽이 격자 알고리즘
void snailcoord(int N)
{
	int size = N;
	int cnt = 1;
	int right = 0, bottom = -1, top = 1;
	int snail[100][100];

	// 달팽이 격자 생성
	for (int i = size; i >= 0; i--)
	{
		for (int j = 0; j < size; j++)
		{
			bottom = bottom + top;
			snail[right][bottom] = cnt++;
		}
		
		size--;

		for (int j = 0; j < size; j++)
		{
			right = right + top;
			snail[right][bottom] = cnt++;
		}
        // 방향 전환
		top *= -1;
	}

	// 달팽이 격자 출력
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cout << snail[i][j] << "\t";
		cout << endl;
	}
}

int main()
{
	while (1)
	{
		int N;
		scanf("%d", &N);
		snailcoord(N);
	}
}

 

해당 알고리즘을 돌리면 다음과 같은 결과를 얻을 수 있습니다. 

 

다음으로는 임의의 두 지점을 입력받고, 두 지점을 꼭지점으로 하는 사각형이 정사각형인지 알아보는 알고리즘을 구현해보겠습니다. 

이를 위해서는 먼저 임의의 두 지점이 달팽이 격자에서 어떤 위치에 있는지 알아야합니다. 가장 쉬운 방법은 위에서 만든 달팽이 격자를 하나씩 만들면서 임의의 두 지점과 맞는지 확인하는 방법입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>

using namespace std;

void snailcoord(int N, int num1, int num2, int coord1[], int coord2[])
{
	int size = N;
	int cnt = 1;
	int right = 0, bottom = -1, top = 1;
	bool flag1 = false, flag2 = false;

	for (int i = size; i >= 0; i--)
	{
		for (int j = 0; j < size; j++)
		{
			bottom = bottom + top;
			if (cnt == num1)
			{
				coord1[0] = right;
				coord1[1] = bottom;
				flag1 = true;
			}
			if (cnt == num2)
			{
				coord2[0] = right;
				coord2[1] = bottom;
				flag2 = true;
			}
			if (flag1 && flag2)
				return;
			cnt++;
		}

		size--;

		for (int j = 0; j < size; j++)
		{
			right = right + top;
			if (cnt == num1)
			{
				coord1[0] = right;
				coord1[1] = bottom;
			}
			if (cnt == num2)
			{
				coord2[0] = right;
				coord2[1] = bottom;
			}
			if (flag1 && flag2)
				return;
			cnt++;
		}

		top *= -1;
	}
}

string checkSquare(int coord1[], int coord2[])
{
	if ((coord1[0] - coord2[0] != 0) && (abs(coord1[0] - coord2[0]) == abs(coord1[1] - coord2[1])))
		return "YES";
	else
		return "NO";
}


int main()
{
	while (1)
	{
		int N, A, B;
		int coord1[2], coord2[2];
		cout << "N, A, B = ";
		scanf("%d %d %d", &N, &A, &B);
		snailcoord(N, A, B, coord1, coord2);
		cout << checkSquare(coord1, coord2) << endl;
	}
}

해당 알고리즘을 돌리면 다음과 같은 결과를 얻을 수 있습니다. 

 

해당 알고리즘은 잘 돌아가지만, 느리다는 치명적인 단점이 있습니다. 이를 해결하기 위해 새로운 코드를 작성 후 이전 코드와 시간 비교를 해봤습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <chrono>

using namespace std;
using namespace chrono;

void snailcoord(int N, int num1, int num2, int coord1[], int coord2[])
{
	int size = N;
	int cnt = 1;
	int right = 0, bottom = -1, top = 1;
	bool flag1 = false, flag2 = false;

	for (int i = size; i >= 0; i--)
	{
		for (int j = 0; j < size; j++)
		{
			bottom = bottom + top;
			if (cnt == num1)
			{
				coord1[0] = right;
				coord1[1] = bottom;
				flag1 = true;
			}
			if (cnt == num2)
			{
				coord2[0] = right;
				coord2[1] = bottom;
				flag2 = true;
			}
			if (flag1 && flag2)
				return;
			cnt++;
		}

		size--;

		for (int j = 0; j < size; j++)
		{
			right = right + top;
			if (cnt == num1)
			{
				coord1[0] = right;
				coord1[1] = bottom;
			}
			if (cnt == num2)
			{
				coord2[0] = right;
				coord2[1] = bottom;
			}
			if (flag1 && flag2)
				return;
			cnt++;
		}

		top *= -1;
	}
}

void snailcoord2(int N, int num1, int num2, int coord1[], int coord2[])
{
	int size = N;
	int cnt = 1;
	int right = 0, bottom = -1, top = 1;
	bool flag1 = false, flag2 = false;

	while (1)
	{
		num1 -= size;
		num2 -= size;

		if ((num1 <= 0) && !flag1)
		{
			coord1[0] = right;
			coord1[1] = bottom + (top * (size + num1));
			flag1 = true;
		}
		if ((num2 <= 0) && !flag2)
		{
			coord2[0] = right;
			coord2[1] = bottom + (top * (size + num2));
			flag2 = true;
		}
		if (flag1 && flag2)
			break;
		bottom += top * size;
		size--;
		num1 -= size;
		num2 -= size;

		if ((num1 <= 0) && !flag1)
		{
			coord1[0] = right + (top * (size + num1));
			coord1[1] = bottom;
			flag1 = true;
		}
		if ((num2 <= 0) && !flag2)
		{
			coord2[0] = right + (top * (size + num2));
			coord2[1] = bottom;
			flag2 = true;
		}
		if (flag1 && flag2)
			break;
		right += top * size;
		top *= -1;
	}
}

string checkSquare(int coord1[], int coord2[])
{
	if ((coord1[0] - coord2[0] != 0) && (abs(coord1[0] - coord2[0]) == abs(coord1[1] - coord2[1])))
		return "YES";
	else
		return "NO";
}


int main()
{
	while (1)
	{
		int N, A, B;
		int coord1[2], coord2[2];
		int coord3[2], coord4[2];
		cout << "N, A, B = ";
		scanf("%d %d %d", &N, &A, &B);

		steady_clock::time_point start1 = steady_clock::now();
		snailcoord(N, A, B, coord1, coord2);
		steady_clock::time_point end1 = steady_clock::now();
		duration<double> sec1 = end1 - start1;
		cout << "Method1 result: " << checkSquare(coord1, coord2) << endl;
		cout << "elapsed time: " << sec1.count() << endl << endl;
		
		steady_clock::time_point start2 = steady_clock::now();
		snailcoord2(N, A, B, coord3, coord4);
		steady_clock::time_point end2 = steady_clock::now();
		duration<double> sec2 = end2 - start2;
		cout << "Method2 result: " << checkSquare(coord1, coord2) << endl;
		cout << "elapsed time: " << sec2.count() << endl << endl;
	}
}

위의 결과처럼, N의 크기가 커질수록 알고리즘의 속도 차이는 더 많이 나게 됩니다.

 

오늘은 C++ 알고리즘에서 자주 다루는 달팽이 격자에 대해서 만들어봤습니다.

관련한 질문이 있으시면 댓글로 달아주세요 :)