C++로 구현하는 라틴 방진(Latin Square) 생성 알고리즘

라틴 방진(Latin Square)은 각 행과 열에 같은 숫자가 정확히 한 번씩만 등장하는 특수한 패턴의 행렬입니다. 다양한 예시를 통해 이 패턴을 자세히 살펴보겠습니다.

1 2
2 1

1 2 3
3 1 2
2 3 1

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

위 예시에서 볼 수 있듯이 라틴 방진은 크기가 다양합니다. 하지만 이 행렬들의 패턴을 잘 관찰해 보면 한 가지 공통된 규칙을 발견할 수 있습니다. 바로 이전 행의 마지막 숫자가 다음 행의 첫 번째 요소로 이동한다는 것입니다.

이것이 바로 라틴 방진에 숨겨진 핵심 패턴입니다. 이제 입력으로 주어진 n에 대해 위와 같은 행렬을 생성하는 프로그램을 작성해 보겠습니다.

알고리즘

• n을 원하는 숫자로 초기화합니다.
• n + 1 값을 가지는 변수를 초기화하고 first_half_end라고 이름 붙입니다.
• 1부터 n까지(양쪽 모두 포함) 반복하는 루프를 작성합니다.
  • first_half_end의 값을 first_half_start라는 변수에 할당합니다.
  • first_half_start가 n에 도달할 때까지 반복하는 루프를 작성합니다.
    • 반복 변수인 first_half_start를 출력합니다.
  • 1부터 first_half_end까지 반복하는 루프를 작성합니다.
    • 반복 변수를 출력합니다.
  • first_half_end의 값을 1 감소시킵니다.
  • 다음 행으로 이동합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>

using namespace std;

void generateLatinSquare(int n) {
   int first_half_end = n + 1;

   for (int i = 1; i <= n; i++) {
      int first_half_start = first_half_end;
      while (first_half_start <= n) {
         cout << first_half_start << " ";
         first_half_start++;
      }

      for (int second_half_start = 1; second_half_start < first_half_end; second_half_start++) {
         cout << second_half_start << " ";
      }
      first_half_end--;
   cout << endl;
   }
   cout << endl;
}

int main(void) {
   generateLatinSquare(2);
   generateLatinSquare(3);
   generateLatinSquare(4);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

1 2
2 1

1 2 3
3 1 2
2 3 1

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

이처럼 각 행이 한 칸씩 순환 이동(circular shift)하는 구조를 활용하면, 크기 n×n의 라틴 방진을 간단한 반복문만으로 효율적으로 생성할 수 있습니다.