[백준][2580][c++] 스도쿠

스도쿠 문제 링크

[문제 풀이]
9*9 인 map의 아무 원소도 없는 입력이 들어올 수 있다는 생각을 해보면, 최적화를 깔끔히 해야 한다는 점이 이 문제에서 core인 것 같다.
1) 입력으로 0인 곳이 될 수 있는 경우의 수를 각각 저장한다.
2) 차례대로 조합을 하는 동시에 새로 넣는 수가 현재 채워진 map에서 스도쿠 조건을 만족하는지 확인한다.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int new_map[10][10];

struct info {
	int y;
	int x;
	vector<int> element;
};

vector<info> comb;

void fill_empty() {
	comb.clear();
	for (int y = 0; y < 9; y++) {
		for (int x = 0; x < 9; x++) {
			if (new_map[y][x] != 0) continue;
			vector<int> width;
			vector<int> height;
			vector<int> rectangle;
			vector<int> number_row = { 1,2,3,4,5,6,7,8,9 };
			vector<int> number_col = { 1,2,3,4,5,6,7,8,9 };

			for (int i = 0; i < 9; i++) {
				if (new_map[i][x] != 0) {
					number_col.erase(find(number_col.begin(), number_col.end(), new_map[i][x]));
				}
				if (new_map[y][i] != 0) {
					number_row.erase(find(number_row.begin(), number_row.end(), new_map[y][i]));
				}
			}

			width = number_row;
			if (width.size() == 1) {
				new_map[y][x] = width[0];
				continue;
			}

			height = number_col;
			if (height.size() == 1) {
				new_map[y][x] = height[0];
				continue;
			}

			int y_start = (y / 3) * 3;
			int x_start = (x / 3) * 3;
			vector<int> number = { 1,2,3,4,5,6,7,8,9 };
			for (int y_c = y_start; y_c < y_start + 3; y_c++) {
				for (int x_c = x_start; x_c < x_start + 3; x_c++) {
					if (new_map[y_c][x_c] == 0) continue;
					number.erase(find(number.begin(), number.end(), new_map[y_c][x_c]));

				}
			}
			rectangle = number;
			if (rectangle.size() == 1) {
				new_map[y][x] = rectangle[0];
				continue;
			}

			vector<int> saved;
			for (int i = 0; i < rectangle.size(); i++) {
				int element = rectangle[i];
				if (find(width.begin(), width.end(), element) != width.end() && find(height.begin(), height.end(), element) != height.end()) {
					saved.push_back(element);
				}
			}

			if (saved.size() == 1) {
				new_map[y][x] = saved[0];
				continue;
			}
			info data;
			data.y = y; data.x = x; data.element = saved;
			comb.push_back(data);

		}
	}
}


void test_new_map() {
	//cout << "\n";
	for (int y = 0; y < 9; y++) {
		for (int x = 0; x < 9; x++) {
			cout << new_map[y][x] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}


bool check_partial(int y, int x) {
	//새로 선택한 경우가 같은 행 혹은 열에 같은 숫자가 있는지, 3*3 크기의 구역에 같은 숫자가 있는지 체크
	map<int, int> width;
	map<int, int> height;
	for (int i = 0; i < 9; i++) {
		if (new_map[y][i] == new_map[y][x] && i != x) return false;
		if (new_map[i][x] == new_map[y][x] && i != y) return false;
	}

	int y_start = (y / 3) * 3;
	int x_start = (x / 3) * 3;
	map<int, int> rectangle;
	for (int y_c = y_start; y_c < y_start + 3; y_c++) {
		for (int x_c = x_start; x_c < x_start + 3; x_c++) {
			if (new_map[y_c][x_c] == new_map[y][x] && (y_c != y && x_c != x)) return false;
		}
	}

	return true;
}

bool permutation(int v_size, int v_index) {
	if (v_size == comb.size()) {
		//test_new_map();
		test_new_map();
		return true;
	}
	else {
		int y = comb[v_size].y;
		int x = comb[v_size].x;
		vector<int> elements = comb[v_size].element;
		for (int j = v_index; j < elements.size(); j++) {
			new_map[y][x] = elements[j];
			if (!check_partial(y, x)) {
				continue;
			}
			bool flag= permutation(v_size + 1, 0);
			if (flag) return flag;
			new_map[y][x] = 0;
		}
		
	}

	return false;
}

int main() {
	int zero = 0;
	for (int y = 0; y < 9; y++) {
		for (int x = 0; x < 9; x++) {
			cin >> new_map[y][x];
			if (new_map[y][x] == 0) zero += 1;
		}
	}

	fill_empty();	//입력으로 0인 곳이 될 수 있는 경우의 수를 각각 저장한다.

	permutation(0, 0);
	//test_new_map();
}

[총평]
푸는데 엄청 오래 걸렸고, 결국에는 다른 사람의 코드 참고를 하였다.
확실히 테스트 케이스가 없어서 내가 생각하는 것에서 어려웠던 것 같다(하지만 꼭 필요한 과정!)
그리고 시간이 타이트 하기 때문에 for문 최적화도 해결해야 한다.

[참고자료]
https://cryptosalamander.tistory.com/59
https://silver-g-0114.tistory.com/135