[백준] 2239-스도쿠(C++)

문제링크:www.acmicpc.net/problem/2239

2239번: 스도쿠

 

일반적인 스도쿠문제와 동일합니다.

 다만,  "제일 작은 경우를 출력한다." 라는 조건이 추가됐습니다.

아래 링크와 같은 방법으로 해결해도 됩니다. 

 

gusdnr69.tistory.com/142

[백준] 2580-스도쿠(C++)

 

저는 직관적인 방법으로 결과를 도출했습니다.

아래는 정답 코드 입니다.

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int arr[9][9] = { 0, };
bool fin = false;
vector <pair <int, int>> zero_vec;

void dfs(int cnt) {
	if (cnt == zero_vec.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << arr[i][j];
			cout << endl;
		}
		fin = true;
		return;
	}
	if (fin == true)
		return;

	for(int i=cnt;i<zero_vec.size();i++){}
	int y = zero_vec[cnt].first;
	int x = zero_vec[cnt].second;

	bool temp[10] = { 0, };
	for (int i = 0; i < 9; i++) {
		temp[arr[y][i]] = 1;
		temp[arr[i][x]] = 1;
	}
	for (int i = y / 3 * 3; i < y / 3 * 3 + 3; i++)
		for (int j = x / 3 * 3; j < x / 3 * 3 + 3; j++)
			temp[arr[i][j]] = 1;

	for (int i = 1; i <= 9; i++)
		if (temp[i] == 0) {
			arr[y][x] = i;
			dfs(cnt + 1);
			arr[y][x] = 0;
		}


}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	for (int i = 0; i < 9; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < 9; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 0)
				zero_vec.push_back(make_pair(i, j));
		}
	}
	dfs(0);

	return 0;
}