마방진 수 구하기

전 시간에 순열에 대해서 재귀를 이용해 구현해 보았다.

DFS(Depth First Search)라고도 불리는 이 방법은, 처음부터 끝까지 탐색해서 찾아보고 다시 올라와서 그 다음 찾는 방식인데 이제 여러분은 DFS 알고리즘을 기본적으로 알고 있는 셈이라고 생각하면 된다. DFS는 결국 Backtracking이라고 불리는 알고리즘 문제와 유사하기 때문에 한번에 순열, DFS, Bactkracking 문제를 풀 어보면서 감을 늘려야 한다. 이번 시간엔 실전 문제를 한번 해볼까 한다. 다음은 문제이다.

3X3 마방진이라는 수열이 있다.

아래 수와 같이, 가로행의 합과, 세로열의 합이 모두 같은 수가 되게 만드는 경우 마방진 수열이라고 한다.

1	2	3
3	2	1
2	2	2

첫번째 열 합 : 1 + 2 + 3 = 6

첫번째 행 합 : 1 + 3 + 2 = 6

TC 50개가 주어지며 각 TC별 수는 1~9까지 9개의 숫자가 중복허용하여 나올 수 있을때, 3X3 마방진 수열이 되는 경우는 각각 몇 번인지 출력하라.

단, 중복되는 수열은 제외한다.

입력:

첫번째 열에 TC개수가 오고, 두번째 열부터는 9개의 수열이 나열된다.

2

1 2 3 3 2 1 2 2 2

2 2 2 2 2 2 2 2 2

출력: 

각 TC 별 3X3 마방진 수열을 갯수를 출력한다.

#1 Case

18

#2 Case

1

여기 까지 문제 이해가 안되거나 모호한게 없다고 생각하고 풀이 방법을 생각해보자.

우선, 문제에서 요구하는 것은 주어진 수 9개를 이용해서 마방진 수열이 되는 경우의 수를 모두 구하는 것인데,

음, 9개를 숫자를 이용해, 9개의 수를 만드는 방법이라고도 할 수 있다. 그럼 9H9 가 되고, 9개의 숫자가 모두 선택됬을때 수열이 마방진인지만 체크하면 될 것 같다.

그리고 모든 수가 같은수면 경우의 수는 1 밖에 나오지 않으며, 전체 수열의 합이 3으로 나누어지지 않으면 3X3 마방진수 를 만들수 없다.

이렇게 어떻게하면 되겠다 가닥이 나오면 복잡도를 먼저 계산해봐야한다. 보통 50개정도의 TC를 2~3초안에 수행해야하기때문에 1초에 1억번의 루프가 가능하다고 가정하면 3억(3초) / 50개(TC갯수) 면 개당 6백만번의 루프까지는 가능하다.

3X3 마방진 수열을 구하는 맥스시간의 경우 9개의 숫자를 선택하는 것이므로 9 X 8 X 7 X 6 X 5 X 4 X 3 X 2 X 1 = 362,880 이므로 어거저거 연산추가해도 충분하다는 결론이 나오므로 코딩에 들어가보자! 코딩은 이전 시간의 순열 구하는 코드를 그대로 이용하도록 하겠다.

#include <stdio.h>

#define MAXN 10

int data[MAXN];

int result[MAXN];

int visited[MAXN];

int gCount;

void printAll(int total) {

for (int i = 0; i < total; ++i) {

printf("%d ", result[i]);

}

printf("\n");

}

int checkAllSame(void) {

for (int i = 0; i < MAXN-2; ++i) {

if (data[i] != data[i + 1]) return 0;

}

return 1;

}

int checkSum(void) {

int sum = 0;

for (int i = 0; i < MAXN - 1; ++i) {

sum += data[i];

}

if (sum % 3) return 1;

return 0;

}

int checkMabangjin(void) {

//가로, 세로 모든 열 계산

int n = result[0] + result[1] + result[2];

if (n != result[3] + result[4] + result[5]) return 0;

if (n != result[6] + result[7] + result[8]) return 0;

if (n != result[0] + result[3] + result[6]) return 0;

if (n != result[1] + result[4] + result[7]) return 0;

if (n != result[2] + result[5] + result[8]) return 0;

return 1;

}

void perm(int n, int r, int depth) {

if (depth == r) {

if (checkMabangjin()) {

gCount++;

printAll(r);

}

return;

}

for (int i = 0; i < n; ++i) {

if (visited[i] != 1) {

visited[i] = 1;

result[depth] = data[i];  // 입력받은 수열에서 하나씩 저장

perm(n, r, depth + 1);

result[depth] = 0;

visited[i] = 0;

}

}

}

int main(void)

{

int n = 9;

int r = 9;

int T;

scanf("%d", &T);

for (int test_case = 1; test_case <= T; ++test_case) {

for (int i = 0; i < MAXN-1; ++i) {

scanf("%d", &data[i]);

}

gCount = 0;

// 모든 수가 같은 경우 마방진 수열은 1개이다.

if (checkAllSame()) {

printf("#%d Case\n%d", test_case, 1);

continue;

}

// 합이 3으로 나눌때 나머지가 있는 경우, 마방진 수를 만들 수 없다.

if (checkSum()) {

printf("#%d Case\n%d", test_case, 0);

continue;

}

perm(n, r, 0);

printf("#%d Case\n%d\n", test_case, gCount);

}

return 0;

}

첫번째 주어진 Test case의 값을 확인하니......말도안되게 8640이 나온다. 이건 뭐지하는 순간, 문제에서 힌트가 있다. 같은 수열인 경우 중복을 제외해야한다는.

그러고 보니 1 2 3 3 2 1 2 2 2 에서 2가 많이 보인다. 저 2라는 카드를 각각 적용했을때 결과적으로 보면 동일한 케이스들이 분명 발생하는데 어떻게 제거해 주어야할까?? 바로 perm 함수 내에서, 조건을 주어 튕겨내야한다. 다음과 같이 for문아래 visited를 확인하기 전에 다음 구문을 추가한다.

if (i > 0 && !visited[i - 1] && (data[i - 1] == data[i])) continue;

노드가 2번째 부터 적용되고(i > 0), 방문학적이 없으며(!visited[i-1], 이전 카드와 지금카드의 값이 같으면(data[i-1] == data[i]) 할필요가 할필요가 없으므로 튕긴다.

for (int i = 0; i < MAXN-1; ++i) {

if (i > 0 && !visited[i - 1] && (data[i - 1] == data[i])) continue;

if (visited[i] != 1) {

visited[i] = 1;

result[depth] = data[i];

perm(n, r, depth + 1);

visited[i] = 0;

result[depth] = 0;

}

}

근데 그래도 값이 720이 나온다....머지??

알고보니, 이 경우는 오름차순 처렴 정렬해야 풀린다. 숫자의 갯수는 9개이므로 bubble 정렬이어도 속도는 전혀 지장이 없다.

void sortBubble(void){

int temp;

for(int i = 0; i < 9; ++i){

for(int j = 0; j < 8; ++j){

if(data[j] > data[j+1]){

temp = data[j];

data[j] = data[j+1];

data[j+1] = temp;

}

}

}

}

가볍게 버블정렬를 구현해주고 확인하면 1번 case의 경우 18개의 답이 나오게된다. 휴~~~

#include <stdio.h>

#define MAXN 10

int data[MAXN];

int result[MAXN];

int visited[MAXN];

int gCount;

int average = 6;

void sortBubble(void){

int temp;

for(int i = 0; i < 9; ++i){

for(int j = 0; j < 8; ++j){

if(data[j] > data[j+1]){

temp = data[j];

data[j] = data[j+1];

data[j+1] = temp;

}

}

}

}

void printAll(int total) {

for (int i = 0; i < total; ++i) {

printf("%d ", result[i]);

}

printf("\n");

}

int checkAllSame(void) {

for (int i = 0; i < MAXN-2; ++i) {

if (data[i] != data[i + 1]) return 0;

}

return 1;

}

int checkSum(void) {

int sum = 0;

for (int i = 0; i < MAXN-1; ++i) {

sum += data[i];

}

if (sum % 3) return 1;

return 0;

}

int checkMabangjin(void) {

//가로, 세로 모든 열 계산

int n = result[0] + result[1] + result[2];

if (n != result[3] + result[4] + result[5]) return 0;

if (n != result[6] + result[7] + result[8]) return 0;

if (n != result[0] + result[3] + result[6]) return 0;

if (n != result[1] + result[4] + result[7]) return 0;

if (n != result[2] + result[5] + result[8]) return 0;

return 1;

}

void perm(int n, int r, int depth) {

if (depth >= r) {

if(checkMabangjin()){

gCount++;

printAll(r);

}

return;

}

for (int i = 0; i < MAXN-1; ++i) {

if (i > 0 && !visited[i - 1] && (data[i - 1] == data[i])) continue;

if (visited[i] != 1) {

visited[i] = 1;

result[depth] = data[i];

perm(n, r, depth + 1);

visited[i] = 0;

result[depth] = 0;

}

}

}

int main(void)

{

int n = 9;

int r = 9;

int T;

scanf("%d", &T);

for (int test_case = 1; test_case <= T; ++test_case) {

for (int i = 0; i < 9; ++i) {

scanf("%d", &data[i]);

}

gCount = 0;

// 모든 수가 같은 경우 마방진 수열은 1개이다.

if (checkAllSame()) {

printf("#%d Case\n%d", test_case, 1);

continue;

}

// 합이 3으로 나눌때 나머지가 있는 경우, 마방진 수를 만들 수 없다.

if (checkSum()) {

printf("#%d Case\n%d", test_case, 0);

continue;

}

sortBubble();

perm(n, r, 0);

printf("#%d Case\n%d\n", test_case, gCount);

}

return 0;

}

오늘 시간되면 보충설명을 적어볼 예정이다.