홀수 마방진 풀기

 이웃 학부에서 홀수 마방진 프로그램을 과제로 받았단 소식을 접하고 동아리 개강총회가 끝나고 시간 들여서 만들어봤습니다. 다른 사람들의 코드와는 달리 굳이 수식을 계산하고 할 필요 없이 그냥 즉흥적으로 생각나는대로 코드를 작성한 것이라서 코드 길이나 시간복잡도에 있어서는 불리하지만 패턴 찾는데는 괜찮았던것 같아요.

 

---

1. 마방진?

 마방진은 다음과 같은 정의를 가집니다.

 - 정사각형 공간에 1부터 차례로 숫자를 적되, 숫자를 중복하거나 빠트리지 않고 가로, 세로, 대각선에 있는 수의 합이 모두 같도록 만든 숫자의 배열을 의미한다. (네이버 지식백과 - 마방진, https://terms.naver.com/entry.nhn?docId=3386690&cid=60206&categoryId=60206, 2019.03.)

 

 동양판 스도쿠라고 생각하시면 이해가 쉬울거라고 생각합니다.

 

1) 3X3 마방진, 가로 세로 대각선 수의 합이 15로 모두 동일하다.

 

 

---

2. 패턴파악

한 변의 길이가 홀수인 마방진은 공식이 존재하기 때문에 크게 어렵지 않습니다. 2학년 과제이니 그리 어렵지 않은 문제를 낸거겠죠? 하지만 전 공식대로 안따라갑니다. 사실 제 방식이 공식인지 아닌지도 모르겠어요. 근데.. 뭐... 공식이겠죠?

 3X3 마방진을 만들기 위해 먼저 다음과 숫자를 같이 작성합니다.

 

 

 이렇게 작성을 하고나면, 가운데 5를 중심으로 가장 가까운 공백부터 차례로 채워나갑니다. 이 때, 채워나가는 공식은 다음과 같습니다.

 

 만일 9와 5 사이의 공백을 채우려 한다면 중심을 기준으로 해당 공백에서 반대쪽으로 가장 멀리 있는 숫자를 채워 넣습니다. 즉, 이미지와 같이 숫자를 넣는거죠.

 

 

 위와 같은 식으로 남은 세 공백도 채우면 1)의 이미지처럼 3X3 마방진이 완성됩니다.

 

 그렇지만 아직 패턴을 파악하기에는 뭔가 부족합니다. 고작 하나만 보고서는 제대로 패턴을 파악할 수 없죠. 그래서 먼저, 5X5, 7X7 마방진도 살펴봅니다. 이 때, 저는 3X3의 방식대로 코드를 작성할 것이기 때문에 완성된 마방진이 아니라 아직 완성 전의 raw 데이터를 봐보겠습니다.

 

좌측은 5X5, 우측은 7X7 마방진 raw이다.

 

 

 이번엔 완성된 마방진을 봐보겠습니다.

 

좌측은 5X5, 우측은 7X7 완성된 마방진이다.

 

 뭔가 패턴이 보이시나요? 패턴이 안보이시는 분을 위해 5X5로 한번 합성을 해보겠습니다.

 

 

 감이 오시나요? 맞습니다. 현재 위 사진을 보면 [23, 15, 3, 11]로 둘러싸인 사각형의 상하좌우 공백부분에 공백 방향의 반대쪽 숫자가 들어와있습니다. 이미지로 보면 다음과 같습니다.

 

 

 이제는 패턴이 보이시리라 생각합니다.

---

3. 코드 구현

 이제 코드를 구현해봅니다. 먼저 raw 데이터를 보관할 공간을 할당합시다. 이 때 공간은 [ (마방진 한 변의 길이) * 2 - 1 ]가 길이가 되는 정사각형 공간을 할당받습니다. 일차원 배열로도 가능하지만 편의를 위해 이차원 배열로 받습니다.

 

	int lineLength = (size * 2 - 1);
	int **map = new int*[lineLength];
	for (int i = 0; i < lineLength; ++i) {
		map[i] = new int[lineLength];
		memset(map[i], 0, sizeof(int) * lineLength);
	}

 이 때, memset을 해주는 이유는 할당받은 공간에 기본 값을 0으로 지정해주기 위함입니다. 이후 코드에서 중요한 역할을 하니 빼시면 안됩니다. 대신 for문으로 일일이 0으로 대입해주는 것은 상관 없습니다. size는 cin^[각주:1]으로 사용자로부터 받습니다.

 

 공간을 할당했으면, 이제 raw 데이터를 입력하는 코드를 작성합니다. 시작은 제일 밑줄 가운데부터 [ x: 1, y: -1] 만큼 증가하니 코드는 다음과 같습니다. 이 때, 일반적으로 x - y 순으로 인덱스를 작성하는 것과 달리 메모리의 효율성을 위해 y - x 순으로 작성합니다. 자세한 내용은 다음 글을 참고하세요.

	int count = 1;
	for (int y = (size - 1) * 2, x = size - 1; y >= size - 1; --y, --x) {
		for (int i = 0; i < size; ++i) {
			map[y - i][x + i] = count++;
		}
	}

 이 때, count 변수는 각 위치에 들어갈 값을 의미합니다. y의 시작이 [ (size - 1) * 2 ]인 이유는 다음과 같습니다. 

 

가로는 col, 세로는 row입니다.

 

 줄 수는 9줄이지만, 마지막 줄의 인덱스는 8이기 때문에 편의를 위해 size에서 1을 뺀 값에 2를 곱한 것입니다. 줄의 끝은 인덱스 4에서 끝나니 size - 1까지만 반복을 진행하도록 했습니다. 입력하는 순서는 다음과 같습니다. [ 1 to 5, 6 to 10, 11 to 15, ..., 21 to 25]

 

 raw 데이터 입력이 완료 되었으면 이제 위치를 영역 밖의 수를 안으로 들여와야합니다. 현재까지 코드를 따라 작성하셨다면 이미지상에 있는 모든 공백 부분은 0으로 채워져 있습니다. 이 때, 우리가 판별하는 공간은 [23, 15, 3, 11] 네 수가 꼭짓점인 정사각형 영역입니다.

 

 

 

 이 때 각 숫자가 이동하는 offset의 절대값은 size만큼이네요. 상황에 맞게 더하거나 빼줍니다. 저는 위 행동을 위 아래, 그리고 좌 우로 나누어 처리했습니다. 조금만 신경쓰면 하나로 처리도 가능할 것 같군요.

 

	int *p = nullptr;
	for (int offsetY = 1; offsetY <= size / 2; ++offsetY) {
		for (int offsetX = -(size / 2); offsetX < size / 2; ++offsetX) {
			p = &(map[size - 1 + offsetY][size - 1 + offsetX]);
			if (*p == 0)
				*p = map[-1 + offsetY][size - 1 + offsetX];
			p = &(map[size - 1 - offsetY][size - 1 + offsetX]);
			if (*p == 0)
				*p = map[lineLength - offsetY][size - 1 + offsetX];

		}
	}

	for (int offsetX = 1; offsetX <= size / 2; ++offsetX) {
		for (int offsetY = -(size / 2); offsetY < size / 2; ++offsetY) {
			p = &(map[size - 1 + offsetY][size - 1 + offsetX]);
			if (*p == 0)
				*p = map[size - 1 + offsetY][-1 + offsetX];

			p = &(map[size - 1 + offsetY][size - 1 - offsetX]);
			if (*p == 0)
				*p = map[size - 1 + offsetY][lineLength - offsetX];
		}
	}

 포인터 p를 사용해 중복 사용되는 코드를 조금 줄여봤습니다. 인덱스 위치는 왜 이렇게 작성하는지 한번 스스로 생각하고 공부해보세요. 위치 감강이 좋아집니다. 머릿속으로만 생각하지 말고, 엑셀이나 다른 프로그램으로 표를 만들어 직접 눈으로 보고 손가락으로 가리키면서 공부해보세요. 조금 더 수월하게 공부할 수 있을겁니다.

 

 이렇게 위 작업까지 마치면 이렇게 공간이 남게 됩니다.

 

5X5 마방진이지만 소스코드상으로는 9X9 공간이 할당되어있다.

 

 구조상 위 이미지처럼 공간에 작성이 되어있기 때문에 우리는 빨간색 공간만 출력하도록 해야합니다. 모든 공간을 출력하면 위처럼 이상하게 출력될거예요.

 

	for (int y = size / 2; y < lineLength - size / 2; ++y) {
		for (int x = size / 2; x < lineLength - size / 2; ++x) {
			cout << setw(4) << map[y][x];
		}
		cout << endl;
	}

 이 때, setw() 를 사용하기 위해서는 iomanip 헤더를 추가해야합니다.

 

 마지막으로 동적 할당을 했다면 해제를 해주는 코드도 작성해야겠죠? 사실 해제하는 코드는 동적 할당을 코드를 작성하면서 함께 쌍으로 작성해주는 것이 좋은 습관입니다. 나중에 작성해야지 하면서 작성하지 않는 경우가 많거든요 :)

 

	for (int i = 0; i < lineLength; ++i) {
		delete[] map[i];
	}
	delete[] map;

 

 

 

---

4. 완료 코드

 이렇게 만든 전체 코드는 다음과 같습니다. 3부터 15까지의 마방진을 출력하기 위해 함수로 실습 내용을 수정했습니다.

 

 

#include <iostream>
#include <iomanip>

using namespace std;

void PrintMabangjin(int size) {
	ios::sync_with_stdio(false);

	cout << "input map size: " << size << endl;

	int lineLength = (size * 2 - 1);
	int **map = new int*[lineLength];
	for (int i = 0; i < lineLength; ++i) {
		map[i] = new int[lineLength];
		memset(map[i], 0, sizeof(int) * lineLength);
	}


	int count = 1;
	for (int y = (size - 1) * 2, x = size - 1; y >= size - 1; --y, --x) {
		for (int i = 0; i < size; ++i) {
			map[y - i][x + i] = count++;
		}
	}

	int *p = nullptr;
	for (int offsetY = 1; offsetY <= size / 2; ++offsetY) {
		for (int offsetX = -(size / 2); offsetX < size / 2; ++offsetX) {
			p = &(map[size - 1 + offsetY][size - 1 + offsetX]);
			if (*p == 0)
				*p = map[-1 + offsetY][size - 1 + offsetX];
			p = &(map[size - 1 - offsetY][size - 1 + offsetX]);
			if (*p == 0)
				*p = map[lineLength - offsetY][size - 1 + offsetX];

		}
	}

	for (int offsetX = 1; offsetX <= size / 2; ++offsetX) {
		for (int offsetY = -(size / 2); offsetY < size / 2; ++offsetY) {
			p = &(map[size - 1 + offsetY][size - 1 + offsetX]);
			if (*p == 0)
				*p = map[size - 1 + offsetY][-1 + offsetX];

			p = &(map[size - 1 + offsetY][size - 1 - offsetX]);
			if (*p == 0)
				*p = map[size - 1 + offsetY][lineLength - offsetX];
		}
	}

	for (int y = size / 2; y < lineLength - size / 2; ++y) {
		for (int x = size / 2; x < lineLength - size / 2; ++x) {
			cout << setw(4) << map[y][x];
		}
		cout << endl;
	}

	cout << endl;

	for (int i = 0; i < lineLength; ++i) {
		delete[] map[i];
	}
	delete[] map;
}

int main(void) {

	for (int i = 3; i < 16; i += 2) {
		PrintMabangjin(i);
	}

	return 0;

}

 

 

 

 

 

 

 

 

 

1. c - in으로 읽습니다. [본문으로]