[BOJ] 2045 - 마방진 (C++)

 

https://www.acmicpc.net/problem/2045

2045번: 마방진

---

풀이

 보편적으로는 세로든 가로든 대각선이든 한 줄의 합을 구했다. 구한 합을 이용하여 지워진 곳의 값을 구하여 바꾸어 주었다. 

 지워진 값을 구할 때 조심해야 할 부분이 있다.

0	0
		0

첫번째 행을 보면 지워진 곳이 두 곳이 있다. 이럴 경우에는 미지수가 두 개이기 때문에 지워진 값을 구할 수 없다. 따라서 이 때는 열을 이용해 지워진 값을 구하도록 구현했다.

 

 

 

 위와 같은 방식으로 구현했을 때, 예외 case가 발생한다.

0
	0
		0

 위처럼 한 대각선의 수를 모두 지워버린 상태라면 한 줄의 합을 구할 수 없다. 이 경우에는 방정식을 세워서 지워진 값을 구했다. 예제 입력으로 방정식을 세워보면,

x	12	12
16	x+4	4
8	8	x+8

 첫번째 행의 지워진 값을 x라고 두고, 행의 합을 기준으로 다른 지워진 값들을 x에 대해 표현한다. 그럼 대각선의 합은 1행의 합과 같기 때문에 3x + 12 = x + 24,  2x = 12, 즉 x = 6 임을 구할 수 있다.

 

 이 방정식을 일반화하여 코드를 구현했다.

---

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <map>
#include <functional>

using namespace std;
using ll = long long;

int arr[10][10];

int main(void) {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	// 마방진 입력
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}
	
	// 예외 : 대각선을 모두 까먹었을 때
	if (!arr[0][0] && !arr[1][1] && !arr[2][2]) {
		vector<int>v;
		v.push_back(arr[0][1] + arr[0][2]);
		v.push_back(arr[1][0] + arr[1][2]);
		v.push_back(arr[2][0] + arr[2][1]);
		int temp = v[0] - v[1] + v[0] - v[2];
		temp = v[0] - temp;
		arr[0][0] = temp / 2;
		arr[1][1] = arr[0][0] + v[0] - v[1];
		arr[2][2] = arr[0][0] + v[0] - v[2];
		
	}

	if (!arr[0][2] && !arr[1][1] && !arr[2][0]) {
		vector<int>v;
		v.push_back(arr[0][0] + arr[0][1]);
		v.push_back(arr[1][0] + arr[1][2]);
		v.push_back(arr[2][1] + arr[2][2]);
		int temp = v[0] - v[1] + v[0] - v[2];
		temp = v[0] - temp;
		arr[0][2] = temp / 2;
		arr[1][1] = arr[0][2] + v[0] - v[1];
		arr[2][0] = arr[0][2] + v[0] - v[2];

	}



	int total = 0;
	// 한 줄의 합 구하기
	// 가로
	for (int i = 0; i < 3; i++) {
		int temp = 0;
		for (int j = 0; j < 3; j++) {
			temp += arr[i][j];
		}
		total = max(total, temp);
	}
	// 세로
	for (int i = 0; i < 3; i++) {
		int temp = 0;
		for (int j = 0; j < 3; j++) {
			temp += arr[j][i];
		}
		total = max(total, temp);
	}
	// 대각선
	total = max(total, arr[0][0] + arr[1][1] + arr[2][2]);
	total = max(total, arr[0][2] + arr[1][1] + arr[2][0]);
	// 미지값 구하기
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			int temp = 0;
			if (arr[i][j]) continue;
			// i 행에 0이 한 개 인지 확인
			bool chk_i = 1;
			for (int k = 0; k < 3; k++) {
				if (k == j) continue;
				if (!arr[i][k]) chk_i = 0;
			}
			
			if (chk_i) {
				for (int k = 0; k < 3; k++) {
					temp += arr[i][k];
				}
				arr[i][j] = total - temp;
				continue;
			}
			// j 열에 0이 한개 인지 확인 필요 x
			for (int k = 0; k < 3; k++) {
				temp += arr[k][j];
			}
			arr[i][j] = total - temp;
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << '\n';
	}
}