2차원 배열의 응용 - 마방진 만들기

안녕하세요!

 

오늘 포스팅할 내용은 2차원 배열의 응용예제, '마방진 만들기'입니다!

거북이 등판의 숫자...

다들 한 번씩은 들어보셨을텐데요.

 

마방진은 어떤 원리가 적용되는지를 간단하게 살펴보고,

C++ 2차원 배열로 채워보도록 하겠습니다.

---

1. 마방진의 원리

마방진은 n * n의 개의 숫자를 n * n 행렬에 배열한 것인데,

가로, 세로, 대각선의 합이 모두 같다는 특징을 가지고 있습니다.

 

n이 2가 아니면 마방진은 항상 존재하구요.

 

간단한 예로 5 * 5 마방진은 이렇게 생겼어요.

1부터 n * n까지 모두 채워져 있는데, 아직까진 배열이 어떻게 채워졌는지 감이 오지 않습니다.

하지만 여기에도 규칙이 있으니, 그것은 1이 반드시 첫 번째 행 중간에 와야한다는 점이에요.

그리고 숫자들을 오름차순으로 하나둘씩 채워나갑니다.

 

다음 숫자는 바로 전 숫자의 윗 행, 다음 열에 채우는데요.

다시 말해, 행의 인덱스를 'i'라고 하고, 열의 인덱스를 'j'라고 했을 때,

다음 숫자의 위치는 (i-1)(j+1)이 된다는 말이에요.

 

그런데 1 다음 숫자인 2를 채우려고 하는데, 처음부터 난관인지 자리가 없네요...

 

그럴 때는 열의 인덱스(=j)만 1증가시키고, 행의 인덱스(=i)는 과감하게 n으로 보내줍니다.

 

 

그리고 3까지는 문제 없이 잘 되었습니다.

 

행은 잘 해결되나 싶었는데, 이제는 열이 문제네요.

하지만 열도 별반 다르지 않습니다.

보낼 자리가 없으면 과감히 윗 행( i + 1), 처음 열( j = 0)로 보내면 됩니다.

 

그리고 5까지는 문제 없지 잘 되는가 싶었는데, 이제는 6이 들어갈 자리에 1이 이미 들어가있네요.

 

 

이럴 때는 살포시 바로 아래로 내려주시면 됩니다. ( i - 1)(j)

 

이런 원리로 채워나가니, 다음과 같이 마방진이 완성되었습니다.

 

2. 마방진 C++로 구현하기

역시나 시간을 많이 잡아먹는 마방진, 이제는 컴퓨터가 스스로 할 수 있도록 C++ 구현해볼께요!

먼저 간단하게 5 * 5 정적 할당으로!

2-1. 정적 할당으로 구현

5 * 5의 2차원 배열을 선언했습니다.

 

그 다음으로 필요한 변수들을 선언하고, 초기화 하겠습니다.

여기서 'i'는 시작 행 인덱스, 'j'는 시작 열 인덱스, k는 1부터 채워나갈 숫자,

nmg는 '나머지'를 표현한 것인데, 이를 선언한 이유는 조금 이따가 알려드릴께요!

 

그리고 반복문을 돌려 배열을 하나둘 씩 채워주도록 하겠습니다.

k는 5 * 5의 배열이므로 25까지 반복해주고, magicNumber[0][2]에는 1을 넣어줍니다.

 

그럼 여기까지 하나 공식처럼 뽑아낼 수 있는 것이 있습니다.

숫자는 1부터 n * n까지 반복되어야 하며,

시작행 인덱스는 무조건 0, 시작열 인덱스는 n / 2가 됩니다.

 

그리고 이제는 '나머지(nmg)'라는 변수를 사용할 차례인데요.

나머지는 말 그대로, 나머지를 구해 저장하는 변수입니다.

나머지는 숫자 변수인 k를 5로 나누어준 나머지를 기억합니다.

 

그 이유는 신기하게도 '숫자 ÷ 마방진의 크기'의 나머지가 0이 될 때마다 숫자를 채우는 방식이 아래 방향이 되요. 한 번 보실까요?

 

그래서 당연히 후속 제어문도 다음과 같이 작성할 수 있겠습니다.

당연히 열 변수인 j는 건들 필요가 없습니다.

 

이제는 k가 5로 나누어 떨어지지 않을 경우를 처리해야 합니다.

당연히 조건이 성립하지 않은 또 다른 경우이므로, else로 묶었구요.

 

행과 열 변수인 i와 j를 1씩 감소, 증가 시킨 후에 조건을 물어보는 이유는 '다음 숫자가 들어갈 위치가 선언한 범위를 초과하지 않았는가?'를 미리 확인해보기 위함입니다.

 

행의 경우 1감소 시켰을 때 0보다 작아진다면, i는 마지막 열인 4가 되어야 합니다.

열의 경우 1증가 시켰을 때, 5가 된다면 j를 0으로 세팅해야 합니다.

 

이러한 상태로 조건 검사를 끝내고, 마방진을 출력해보도록 하겠습니다.

역시 변수가 많아져서 m까지 오게 되었습니다.

 

5 * 5 마방진이 출력됩니다.

 

2-2. 동적 할당으로 구현

이제는 사용자로부터 임의의 숫자를 넘겨 받아 동적 할당으로 구현해보도록 하겠습니다.

단, 사용자의 입력값은 n에 저장하고, n은 편의상 홀수로만 받겠습니다.

 

2차원 배열을 선언하고,

 

정적 할당으로 짜볼테 설명드렸던 것처럼, 시작열을 n / 2로, k는 n * n 까지 반복하며,

nmg는 k를 n으로 나눈 나머지 값을 넣겠습니다.

 

행, 열 인덱스 변환도 사용자 입력값을 변수로 넣어줬어요.

 

력도 행, 열 모두 n까지 반복하며 뽑아보겠습니다.

그리고 실행하겠습니다!

짝수 입력받으면 거절 메시지도 잘 나오구요.

임의의 숫자 9를 입력해보겠습니다.

네. 9*9 마방진이 잘 출력되네요! : )

 

---

지금까지 2차원 배열을 활용한 마방진 만들기에 대해 포스팅하였습니다.

 

다음 시간에 뵙겠습니다!!