c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q45 오직 하나뿐인 OX

4 X 4 매트릭스에 O 또는 X가 채워져 있다. 그리고 각 행과 열에 O의 개수를 카운트한다. (아래 그림 참조)

위 매트릭스는 1111, 1111 2개의 숫자로 표현할 수 있다.

그런데, 아래 배열 역시 동일하게 1111, 1111로 표현할 수 있다.

이런 경우, 위 2개의 매트릭스는 서로 형제 관계에 있다고 하자.

(1111, 1111이라는 동일한 부모 숫자를 가지므로)

[문제] 형제가 없는, 즉 외동인 OX 배열의 개수는?

예를 들면 아래 배열은 3211, 4201로 나타낼 수 있는 유일한 배열이므로 외동이다.

 

 

[알고리즘]

먼저 제일 간단한 케이스인 2 X 2 매트릭스에 대해서 살펴보자.

아래 2개의 배열은 서로 형제이다.

위 케이스에 대해서만 형제이고, 나머지 배열들은 모두 외동이다.

이제 2 X 3 매트릭스에 대해서 살펴보자.

위 물음표에 뭐가 오든지 위 배열은 형제가 존재한다.

아래 배열도 마찬가지.

3 X 3 매트릭스에 대해서 살펴보자. 아래 배열 역시 ?에 뭐가 오든 형제가 존재한다.

아래 배열 등도 마찬가지

이를 일반화하면

위와 같은 관계가 존재하면 형제가 있다.

임의의 row1, row2, col1, col2에 대해서

matrix[row1][col1] != matrix[row1][col2] 이면서

matrix[row1][col1] != matrix[row2][col1] 이면서

matrix[row2][col1] != matrix[row2][col2] 이면

형제가 존재한다.

이런 경우를 제외하고 카운트하면 된다.

 

아래는 코드.

#include <stdio.h>
#include <stdbool.h>
#define N 4
int matrix[N][N] = { 0 };
int cnt = 0;
void solve(int matrix[][N], int row, int col);
bool checkMatrix(int matrix[][N]);
int main() {
    solve(matrix, 0, 0);
    printf("cnt = %d\n", cnt);
}
void solve(int matrix[][N], int row, int col) {
    if (row == N) {
        if (checkMatrix(matrix) == true)
            cnt++;
        return;
    }
    for (int i = 0; i <= 1; i++) {
        matrix[row][col] = i;
        if (col == N - 1)
            solve(matrix, row + 1, 0);
        else
            solve(matrix, row, col + 1);
    }
}
bool checkMatrix(int matrix[][N]) {
    int row1, row2;
    int col1, col2;
    for (row1 = 0; row1 < N - 1; row1++) {
        for (row2 = row1 + 1; row2 < N; row2++) {
            for (col1 = 0; col1 < N - 1; col1++) {	
                for (col2 = col1 + 1; col2 < N; col2++) {
                    if (matrix[row1][col1] == matrix[row1][col2])
                        continue;
                    if (matrix[row1][col1] == matrix[row2][col1])
                        continue;
                    if (matrix[row2][col1] != matrix[row2][col2])
                        return false;
                }
            }
        }
    }
    return true;
}

 

정답은 6902개.

 

그런데 위 코드는 4 x 4칸을 모두 채운 후에 매트릭스를 검사하기 때문에 시간이 오래 걸린다.

매트릭스를 채워나가는 족족 바로바로 검사를 해서 걸러내면 시간을 단축시킬 수 있다.

아래와 같이 함수를 수정하면 된다.

void solve(int matrix[][N], int row, int col) {
    if (row == N) {
        cnt++;
        return;
    }
    for (int i = 0; i <= 1; i++) {
        matrix[row][col] = i;
        if (col == N - 1) {
            if (checkMatrix(matrix, row) == false)	// row가 모두 채워지면 검사
                continue;
            solve(matrix, row + 1, 0);
        }
        else
            solve(matrix, row, col + 1);
    }
}
bool checkMatrix(int matrix[][N], int row) {
    int row1, row2;
    int col1, col2;
    for (row1 = 0; row1 <= row - 1; row1++) {
        for (row2 = row1 + 1; row2 <= row; row2++) {
            for (col1 = 0; col1 < N - 1; col1++) {
                for (col2 = col1 + 1; col2 < N; col2++) {
                    if (matrix[row1][col1] == matrix[row1][col2])
                        continue;
                    if (matrix[row1][col1] == matrix[row2][col1])
                        continue;
                    if (matrix[row2][col1] != matrix[row2][col2])
                        return false;
                }
            }
        }
    }
    return true;
}