파이썬으로 라틴 방진(Latin Square) 생성하는 방법

라틴 방진(Latin Square)은 각 행과 열에 서로 다른 숫자가 정확히 한 번씩만 나타나는 특수한 패턴을 가진 n×n 행렬입니다. 조합론, 통계학의 실험 설계, 스도쿠 퍼즐 등 다양한 분야에서 활용되는 개념입니다.

크기별 예시를 통해 패턴을 하나씩 살펴보겠습니다.

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에 따라 다양한 크기로 생성됩니다. 행렬의 패턴을 자세히 관찰해 보면 한 가지 중요한 규칙을 발견할 수 있습니다. 바로 이전 행의 마지막 숫자가 다음 행의 첫 번째 요소로 이동한다는 것입니다.

예를 들어 3×3 라틴 방진을 보면, 첫 번째 행 '1 2 3'의 마지막 숫자인 3이 두 번째 행 '3 1 2'의 첫 번째 요소로 배치되어 있습니다. 이것이 라틴 방진에 숨겨진 핵심 패턴입니다.

이제 입력값 n이 주어졌을 때 위와 같은 행렬을 생성하는 프로그램을 작성해 보겠습니다.

알고리즘

1. n을 원하는 숫자로 초기화합니다.
2. n + 1 값을 저장하는 변수 first_half_end를 초기화합니다.
3. 1부터 n까지(양 끝 포함) 반복하는 루프를 작성합니다.
   • first_half_end의 값을 first_half_start 변수에 할당합니다.
   • first_half_start가 n에 도달할 때까지 반복하며 현재 값을 출력합니다.
   • 1부터 first_half_end까지 반복하며 값을 출력합니다.
   • first_half_end의 값을 1 감소시킵니다.
   • 다음 행으로 이동합니다.

이 알고리즘의 시간 복잡도는 O(n²)로, n×n 크기의 모든 요소를 한 번씩 출력해야 하므로 최적의 성능입니다.

구현

다음은 위 알고리즘을 파이썬으로 구현한 코드입니다.

def generateLatinSquare(n):
    first_half_end = n + 1

    for i in range(1, n + 1):
        first_half_start = first_half_end
        while (first_half_start <= n):
            print(first_half_start, end=" ")
            first_half_start += 1

        for second_half_start in range(1, first_half_end):
            print(second_half_start, end=" ")
        first_half_end -= 1
        print()
    print()

if __name__ == "__main__":
    generateLatinSquare(2)
    generateLatinSquare(3)
    generateLatinSquare(4)

실행 결과

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

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

입력값 2, 3, 4에 대해 각각 올바른 크기의 라틴 방진이 생성된 것을 확인할 수 있습니다. 이 코드를 응용하면 리스트 형태로 결과를 반환하거나, 문자·기호 기반의 라틴 방진을 만드는 것도 가능합니다.