[성실코딩 13일차] 백준 #2580 수도쿠 / Backtracking *

정답률은 낮지만 그냥 딱 생각했을 때 backtracking 으로 하면 쉬울꺼라고 예상했는데 

아아악!!!!!!! 화난다!! 

꼼꼼하게 보는 능력 키우기!!

어쨋든 맞앗지만, 이거 file 읽어오는 걸로 한번 시도해보기!

3*3 정사각형 확인하는 방법

//적고 싶은 소스코드를 적기
#include <iostream>
#include <cstring>

using namespace std;

int table[9][9];
int visited[10] = { 0, };// 0~9

bool checkRow(int _x) {
	memset(visited, 0, sizeof(int)*10);
	for (int i = 0; i < 9; i++) {
		int value = table[_x][i];
		if (visited[value] == 0) {
			visited[value] = 1;
		}
		else if(value!=0){
			return false;
		}
	}
	return true; // 수도쿠 통과
}

bool checkCol(int _y) {
	memset(visited, 0, sizeof(int) * 10);
	for (int i = 0; i < 9; i++) {
		int value = table[i][_y];
		if (visited[value] == 0) {
			visited[value] = 1;
		}
		else if (value != 0) {
			return false;
		}
	}
	return true; // 수도쿠 통과
}

bool checkSquare(int _x, int _y) {
	memset(visited, 0, sizeof(int) * 10);
	int new_x = _x - (_x % 3);
	int new_y = _y - (_y % 3);

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			int value = table[new_x + i][new_y + j];
			if (visited[value] == 0) {
				visited[value] = 1;
			}
			else if(value!=0){
				return false;
			}
		}
	}
	return true;
}

bool check(int _x, int _y) {

	if (checkRow(_x) == false) { // 가로줄 체크
								 // 가로줄에 중복 숫자가 있다면
		return false;
	}
	if (checkCol(_y) == false) { // 세로줄 체크
		return false;
	}
	if (checkSquare(_x, _y) == false) { // 3*3 정사각형 체크
										// 중복 숫자가 있다면
		return false;
	}

	// 위의 3가지 조건을 모두 통과했다면,
	return true;
}

bool findZero(int *_x, int *_y) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {

			if (table[i][j] == 0) {
				*_x = i;
				*_y = j;
				return true;
			}
		}
	}
	return false;
}

bool go() 
{
	int x;
	int y;
	
	if (findZero(&x, &y) == false) { // 수도쿠에 모두 값이 채워졌을 경우

		return true;
	}


	for (int k = 1; k <= 9; k++) {
		table[x][y] = k;
		if (check(x, y) == false) {
			continue;
		}
		else {
				//통과했다면 다음 숫자 찾기.
				if (go() == true) { // 반환값이 true라면 끝!
					return true;

				}
				else { // false일 경우 다른 값 찾기
					table[x][y] = 0;
				}
			}
		}
	table[x][y] = 0;
	return false;
}

int main() {

	// 입력
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> table[i][j];
		}
	}

	// 연산
	go();

	// 출력
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout<< table[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}