마방진
문제 해석
3x3마방진을 완성시키는 문제입니다.
3x3배열에 최대 3개의 칸이 지워져있을때, 마방진의 규칙에 부합하는 숫자를 채워야 합니다.
모든 수는 20,000을 넘지 않습니다.
설계(20)
마방진 규칙을 활용한 구현문제입니다.
마방진은 가로, 세로, 대각선의 수들의 합이 모두 같다는 성질을 가지고 있습니다.
그렇기 때문에, 3개의 칸에 숫자가 연속으로 채워져있는 곳을 찾아서 기준이 되는 합을 찾아서, 빈칸을 채워넣으면 됩니다.
여기서, 반례가 생기게 되는데 다음 아래와 같습니다.
0 1 6
3 0 7
4 9 0
8 1 0
3 0 7
0 9 2
위처럼 한 대각선이 모두 지워진 경우, 기준이 되는 합을 구할 수 없습니다.
이런 경우, 수학 공식을 이용합니다.
모든 수의 합을 3으로 나누었을 경우가 각 선의 합이 되야합니다.
이 성질을 이용해서 6개수의 합을 구하고 2로 나누어주면 기준 합을 구할 수 있습니다.
그 후, 지워진 개수를 카운트해서 재귀 형태로 채울 수 있는 곳을 차례대로 채웁니다.
구현(30)
코드
#include <iostream>
#include <algorithm>
using namespace std;
int arr[3][3];
int total_cnt;
int sum;
bool flag;
int find_sum(){
for (int i = 0; i< 3; i++){
if (arr[i][0] && arr[i][1] && arr[i][2]) return arr[i][0]+arr[i][1]+arr[i][2];
if (arr[0][i] && arr[1][i] && arr[2][i]) return arr[0][i] + arr[1][i] + arr[2][i];
}
if (arr[0][0] && arr[1][1] && arr[2][2]) return arr[0][0]+ arr[1][1] + arr[2][2];
if (arr[0][2] && arr[1][1] && arr[2][0]) return arr[0][2] + arr[1][1] + arr[2][0];
int max_sum = 0;
for (int i = 0 ; i < 3; i++){
for (int j= 0;j<3;j++){
max_sum += arr[i][j];
}
}
return max_sum/2;
}
int find_num(int x, int y){
int cnt = 0;
int tmp_sum = 0;
for (int i = 0 ; i<3;i++){
if (!arr[x][i]) cnt++;
tmp_sum += arr[x][i];
}
if (cnt==1) return sum - tmp_sum;
cnt = 0;
tmp_sum = 0;
for (int i = 0 ; i<3;i++){
if (!arr[i][y]) cnt++;
tmp_sum += arr[i][y];
}
if (cnt==1) return sum - tmp_sum;
if ((x+y)%2==0){
cnt = 0;
tmp_sum = 0;
for (int i = 0 ; i<3;i++){
if (!arr[i][i]) cnt++;
tmp_sum += arr[i][i];
}
if (cnt==1) return sum - tmp_sum;
cnt = 0;
tmp_sum = 0;
for (int i = 0 ; i<3;i++){
if (!arr[i][2-i]) cnt++;
tmp_sum += arr[i][2-i];
}
if (cnt==1) return sum - tmp_sum;
}
return -1;
}
void backtrack(int cnt){
if (flag) return;
if (cnt ==0){
for (int i = 0; i < 3; i++){
for (int j=0 ;j <3;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
flag = true;
return;
}
for (int i = 0 ;i < 3;i++){
for (int j= 0; j<3; j++){
if (arr[i][j]) continue;
int num = find_num(i,j);
if (num==-1) continue;
arr[i][j] = num;
backtrack(cnt-1);
}
}
}
int main(){
for (int i=0 ;i < 3;i++){
for (int j=0;j<3; j++){
scanf("%d",&arr[i][j]);
if (arr[i][j] ==0) total_cnt++;
}
}
sum = find_sum();
backtrack(total_cnt);
return 0;
}
디버깅
처음에, 위에서 언급한 반례를 생각치 못했습니다.
반례를 알고 나서도 로직을 잘못 짰습니다.
각 라인의 숫자합의 최대값 + 1을 기준합으로 설정해서 마방진 규칙이 깨지는 경우가 발생하였습니다.
코드(최적화)
크로아티아 올림피아드 대회에도 나온 문제로 솔루션을 제공합니다.
지워진 부분이 1개인 좌표를 찾는데 아주 신박한 방법을 사용하였습니다.
!arr[i][j]으로 0인 개수를 카운트하는 방식을 이용하였습니다. (아주 유용한 방법이어서 나중에도 활용할 것 같습니다)
또한, 재귀함수를 사용하지 않고 무조건 3번 반복하게 구현하여 아주 깔끔한 코드가 나온 것 같습니다.
#include <iostream>
using namespace std;
int arr[3][3];
int sum;
int find_sum(){
for (int i = 0; i< 3; i++){
if (!(!arr[i][0] + !arr[i][1] + !arr[i][2])) return arr[i][0]+arr[i][1]+arr[i][2];
if (!(!arr[0][i] + !arr[1][i] + !arr[2][i])) return arr[0][i] + arr[1][i] + arr[2][i];
}
if (!(!arr[0][0] + !arr[1][1] + !arr[2][2])) return arr[0][0]+ arr[1][1] + arr[2][2];
if (!(!arr[0][2] + !arr[1][1] + !arr[2][0])) return arr[0][2] + arr[1][1] + arr[2][0];
int max_sum = 0;
for (int i = 0 ; i < 3; i++){
for (int j= 0;j<3;j++){
max_sum += arr[i][j];
}
}
return max_sum/2;
}
int main(){
for (int i=0 ;i < 3;i++){
for (int j=0;j<3; j++){
scanf("%d",&arr[i][j]);
}
}
sum = find_sum();
for (int k = 0;k<3;k++){
for (int i = 0 ; i < 3; i++){
for (int j=0;j<3;j++){
if (!arr[i][j] && (!arr[i][0] + !arr[i][1] + !arr[i][2])== 1) arr[i][j] = sum - arr[i][0] - arr[i][1] - arr[i][2];
if (!arr[i][j] && (!arr[0][j] + !arr[1][j] + !arr[2][j])== 1) arr[i][j] = sum - arr[0][j] - arr[1][j] - arr[2][j];
}
}
}
for (int i =0 ;i<3 ;i++){
for (int j=0;j<3;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
제출결과
0 ms
마무리
마방진 규칙을 적용한 구현문제였습니다.
반례를 생각치 못했고, 해결방법을 찾는데 오래걸렸습니다.