올해 퀄 라운드의 마지막 문제는 라틴 스퀘어를 만드는 문제였다. 라틴 스퀘어를 만드는 것 자체는 어렵지 않은 문제이지만, 이번에는 주 대각선의 합(trace)이 특정한 값이 되어야 한다는 조건이 있어서 상당히 어려웠다.

  1. 관찰
    1. N+1, N2-1
    2. 그 외의 경우
  2. 라틴 스퀘어 채우기
    1. 대각선 찾기
    2. 다른 방법

문제 링크
라틴 스퀘어는 각 행과 열에 1..N 이 각각 한 번씩만 등장하는 N x N 행렬이다.

관찰

문제를 보고 자연스레 떠오르는 접근은 “대각선을 먼저 채운 다음 나머지 칸을 채워보자” 이다. 다만 일부가 채워져 있는 라틴 스퀘어를 완성하는 것은 일반적으로 NP-Complete1에 속한다는 문제가 있다. 해법이 보이지 않으니 우선 Test Set 1 (2 ≤ n ≤ 5)을 해결하는 완전 탐색 코드를 작성하고 출력을 살펴보자.

N+1, N2-1

N ≥ 4일 때의 출력을 살펴보면 trace가 N+1, N2-1 인 경우를 제외하고는 모두 라틴 스퀘어가 존재함을 알 수 있다. trace = N+1 인 경우부터 살펴보면, 대각선이 다음과 같아서 마지막 행에 1을 둘 수 없으므로 완성이 불가능하다.

1
  1
   ...
      1
        2 <-- 1이 들어갈 자리는?

그리고 같은 이유로 trace = N2-1 인 경우에도 라틴 스퀘어가 존재하지 않는다.

N
  N
   ...
      N
        N-1 <-- N이 들어갈 자리는?

즉 1 ≤ x ≤ N 인 x가 대각선에 N-1번 등장할 경우 라틴 스퀘어를 완성할 수 없다.

그 외의 경우

그렇다면 나머지 경우에는 항상 라틴 스퀘어를 완성할 수 있을까? 일단 한 가지 수가 N-1번 등장하는 것은 피할 수 있다:

N+2   = 1, ..., 1, 1, 3  # x = 1, y = 3
      = 1, ..., 1, 2, 2

3N+2  = 3, ..., 3, 3, 5  # x = 3, y = 5
      = 3, ..., 3, 4, 4
      = 3, ..., 3, 2, 6

N^2-2 = N, ..., N, N,   N-2  # x = N, y = N-2
      = N, ..., N, N-1, N-1
  1. N+1 < K < N2-1 인 K에 대해서 K = (N-1)x + y (1 ≤ x, y ≤ N, x ≠ y) 라고 하자.
  2. 조건으로부터 항상 y < N-1 이거나 x < N 임을 알 수 있고,
  3. K = (N-3)x + (x-1) + (x-1) + (y+2) 혹은 K = (N-2)x + (x+1) + (y-1) 으로 다시 쓸 수 있다.
  4. 따라서 같은 수가 N-1번 등장하는 표현을 N-2번 등장하는 표현으로 바꿀 수 있다.

그리고 대각선 위에 같은 수가 N-1번 등장하지 않는 경우 항상 라틴 사각형을 완성할 수 있다2.

물론 대회에서 선행 연구를 찾을 수 있는 것도 아니고, 이를 직접 증명하는 것은 무리이다. 실제로는 답이 존재할 경우 아래에서 설명할 알고리즘의 연산이 빠르게 완료된다는 사실을 이용, 몇 가지 크기에 대해 모든 입력을 직접 수행해보면서 확인했다.

라틴 스퀘어 채우기

라틴 스퀘어의 특징으로는 “라틴 스퀘어의 어느 두 행을 교환해도 라틴 스퀘어”라는 점이 있다. 여기서 직관적으로 라틴 스퀘어를 위에서부터 한 줄씩 만들어도 괜찮을 것이란 생각이 떠오른다3.

라틴 스퀘어의 각 행을 채우는 방법은 여러 가지가 있겠지만, 대회중에는 구현은 조금 길지만 아이디어가 간단한 이분 매칭을 이용했다. 각 열에 대해 해당하는 칸에 들어갈 수 있는 수 모두와 간선을 이어주고 이분 매칭을 수행하면 끝!

예를 들어 5 x 5 에서 trace = 7 인 경우를 살펴보자.

5 1 2 3 4  # 대각선은 5, 5, 1, 1, 1
1 5 3 4 2
2 4 1 5 3  # 여기까지 채운 상태
? ? ? 1 ?
? ? ? ? 5
(4, 1) 1 2 3 4 5 (4, 2) (4, 3) (4, 4) (4, 5)

위와 같이 3번째 행까지 채워져 있는 상태에서 4번째 행의 각 열을 왼쪽부터 (4,1), (4,2), … 로 표현하면 4번째 행을 채우기 위한 이분 그래프는 다음과 같이 구성된다:

  • (4,1)은 첫 번째 열에 1, 2, 5가 올 수 없으므로 3, 4와 연결
  • (4,2)는 두 번째 열에 1, 4, 5가 올 수 없으므로 2, 3과 연결
  • (4,3)은 세 번째 열에 1, 2, 3이 올 수 없으므로 4, 5와 연결
  • (4,4)는 대각선 위의 칸이므로 1과 연결
  • (4,5)는 다섯 번째 열에 2, 3,4가 올 수 없으며 1은 (4,4)에 들어가야 하므로 5와 연결

이렇게 만든 그래프에 이분 매칭을 수행하여 행을 완성할 수 있고, 이를 반복하면 라틴 스퀘어가 완성된다.

대각선 찾기

size = 5, trace = 7

diagonal: 1,1,1,2,2    2,2,1,1,1
  result: FAIL         SUCCESS
          1 2 3 4 5    2 1 3 4 5
          2 1 4 5 3    1 2 4 5 3
          5 4 1 3 ?    3 5 1 2 4
                2      4 3 5 1 2
                  2    5 4 2 3 1

사실 대각선을 미리 채워둔 상태에서는 단순히 위에서부터 한 행씩 그리디하게 채우는 방법으로는 채우지 못하는 경우가 존재한다. 하지만 이런 경우에도 대각선 위 원소들의 순서만 바꾸면 해결할 수 있고, 대부분의 순서에 대해서는 이 방법을 통해 문제 없이 채울 수 있으므로 대각선을 채우는 부분은 완전 탐색으로 구현했다.

#include<cstdio>
#include<set>
#include<queue>
using namespace std;

int n, trace;
vector<vector<int>> square;
vector<set<int>> row_missing;
vector<set<int>> col_missing;

void print_square() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", square[i][j]);
        }
        puts("");
    }
}

vector<vector<int>> graph;
vector<int> row_match, col_match;

bool find_match(int source)
{
    vector<int> from(row_match.size(), -1);
    int now, match;
    from[source] = source;
    queue<int> q;
    q.emplace(source);
    bool found_path = false;
    while (!found_path && !q.empty()) {
        now = q.front(); q.pop();
        for (int i: graph[now]) {
            match = i;
            int next = col_match[match];
            if (now != next) {
                if (next == -1) {
                    found_path = true;
                    break;
                }
                if (from[next] == -1) {
                    q.emplace(next);
                    from[next] = now;
                }
            }
        }
    }

    if (!found_path) return false;

    while (from[now] != now) {
        int aux = row_match[now];
        row_match[now] = match;
        col_match[match] = now;
        now = from[now];
        match = aux;
    }

    row_match[now] = match;
    col_match[match] = now;
    return true;
}

void fill_row(int i) {
    graph.clear();
    row_match.clear();
    col_match.clear();

    graph.resize(n + 10);
    row_match.resize(n + 10, -1);
    col_match.resize(n + 10, -1);

    for (int j = 1; j <= n; j++) {
        if (square[i][j]) continue;

        for (int k = 1; k <= n; k++) {
            if (!row_missing[i].count(k)) continue;
            if (!col_missing[j].count(k)) continue;

            graph[j].emplace_back(k);
        }
    }

    for (int j = 1; j <= n; j++) {
        if (square[i][j]) continue;
        if (!find_match(j)) throw 0;
    }

    for (int j = 1; j <= n; j++) {
        if (square[i][j]) continue;
        square[i][j] = row_match[j];
    }
}

bool fill_square()
{
    auto bak_square = square;
    auto bak_row_missing = row_missing;
    auto bak_col_missing = col_missing;

    try {
        for (int i = 1; i <= n; i++) {
            fill_row(i);
            for (int j = 1; j <= n; j++) {
                col_missing[j].erase(square[i][j]);
                row_missing[i].erase(square[i][j]);
            }
        }
        return true;
    } catch (...) {
        square = bak_square;
        row_missing = bak_row_missing;
        col_missing = bak_col_missing;
        return false;
    }
}

bool fill_diag(int i, int sum)
{
    if (i > n) return sum == trace && fill_square();

    for (int k = min(n, trace-sum-(n-i)); k > 0; --k) {
        if (!row_missing[i].count(k)) continue;
        if (!col_missing[i].count(k)) continue;

        int nsum = sum + k;
        row_missing[i].erase(k);
        col_missing[i].erase(k);
        square[i][i] = k;
        if (fill_diag(i + 1, nsum)) return true;
        square[i][i] = 0;
        col_missing[i].emplace(k);
        row_missing[i].emplace(k);
    }

    return false;
}

void build_latin_square()
{
    if (trace == n * n - 1 || trace == n * n + 1) throw 0;

    square.clear();
    row_missing.clear();
    col_missing.clear();

    square.resize(n+1, vector<int>(n+1, 0));
    row_missing.resize(n+1);
    col_missing.resize(n+1);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            row_missing[i].emplace(j);
            col_missing[i].emplace(j);
        }
    }

    if (!fill_diag(1, 0)) throw 0;
}

int main()
{
    int T;
    for (int C = scanf("%d", &T); T--; C++) {
        printf("Case #%d: ", C);
        scanf("%d%d", &n, &trace);
        try {
            build_latin_square();
            puts("POSSIBLE");
            print_square();
        } catch (...) {
            puts("IMPOSSIBLE");
        }
    }
    return 0;
}

다른 방법

사실 이 문제는 케이스를 잘 나누고 규칙에 따라 채우는 방법[4][5]으로도 깔끔하게 해결할 수 있다.

  1. Charles J. Colbourn, The complexity of completing partial Latin squares, Discrete Applied Mathematics (1984) ↩

  2. Chang, G., Complete Diagonals of Latin Squares, Canadian Mathematical Bulletin (1979) ↩

  3. Every Latin rectangle can be completed to a Latin square. ↩