백준 2239 스도쿠 (C++)

2239번: 스도쿠

백트래킹을 이용한 문제이다. 문제에서는 스도쿠 판이 모두 채워진 결과를 원하고 있다. 즉 0을 모두 채운 결과이다. 우선 스도쿠 판을 입력받을 때 0인 경우의 좌표를 벡터v에 저장을 해주었다. 그 후 dfs를 돌면서 v[depth] 좌표를 기준으로 1부터 시작하여 판을 채워주었다. 이때 스도쿠의 조건을 만족하지 못하면 다음 값으로 채워주면서 depth를 1씩 더해가며 이를 반복하였다. 이때 depth == v.size()를 만족하는 경우, 즉 0에 해당하는 좌표에 모두 값을 채워 더이상 0이 없을 경우 시작을 1부터 해주었기 때문에 처음 조건에 만족하는 경우가 무조건 가장 작은 수에 해당하게 되므로 이를 출력하고 check = true로 바꿔주었다. 그 후의 백트래킹으로 인한 재귀는 check에 의해 걸러지게 되어 최초로 조건에 만족하는 경우만 출력해주게 된다.
생각보다 오래 걸린 문제였다. 백트래킹을 이용한 구현에는 쉽게 접근할 수 있었다. 처음에는 depth == v.size()에 도착했을 때 0이 있는지 확인하는 것과 이를 만족할 경우 따로 result배열에 저장하여 다음에 도착하는 값과 비교하여 저장하는 로직이 있었는데 이떄문인지 시간 초과가 계속해서 발생하여 이를 해결하는 과정에서 시간이 오래 걸렸다. 간단히 제거해주면서 해결할 수 있었고 이를 통해 조건을 확실히 해주어야 한다는 점을 깨달았다.

#include <iostream>
#include <vector>

using namespace std;

string A[9];
vector<pair<int, int>> v;
bool check;

bool step1(int y, int x, char val) {
	for (int i = 0; i < 9; i++) {
		if (A[y][i] == val || A[i][x] == val) return false;
	}

	return true;
}

bool step2(int y, int x, char val) {
	int s = (y / 3) * 3;
	int e = (x / 3) * 3;

	for (int i = s; i < s + 3; i++) {
		for (int j = e; j < e + 3; j++) {
			if (A[i][j] == val) return false;
		}
	}

	return true;
}

void dfs(int depth) {
	if (check) return;

	if (depth == v.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << A[i][j];
			}
			cout << "\n";
		}

		check = true;

		return;
	}

	int y = v[depth].first;
	int x = v[depth].second;
	if (A[y][x] != '0') return;

	for (int i = 1; i <= 9; i++) {
		char val = i + '0';
		if (!step1(y, x, val) || !step2(y, x, val)) continue;

		A[y][x] = val;
		dfs(depth + 1);
		A[y][x] = '0';
	}
}

void solution() {
	dfs(0);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 0; i < 9; i++) {
		cin >> A[i];
		for (int j = 0; j < 9; j++) {
			if (A[i][j] == '0') v.push_back({ i,j });
		}
	}

	solution();
	
	return 0;
}