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

이 문제는 백트래킹 문제이다.

 

시간 복잡도를 조금이라도 줄이려면 애초에 백트래킹 탐색을 할 때 사전식으로 앞서도록 탐색하게 만들면 된다.

 

어떤 좌표 (y, x)가 있을 때, 이를 3으로 나눴다가 3으로 곱하면 해당 칸의 시작 인덱스를 구할 수 있다. 이걸 이용하면 좀 더 쉽게 구현할 수 있다. 물론 이는 0부터 시작해서 8로 끝나는 인덱스를 이용할 때 활용 가능하다.

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

#define SIZE 9

int board[SIZE][SIZE];

void input() {
	for (int y = 0; y < SIZE; y++) {
		for (int x = 0; x < SIZE; x++) {
			char c;
			cin >> c;

			board[y][x] = c - '0';
		}
	}
}

pair<int, int> findStart(int y, int x) {
	y /= 3;
	x /= 3;
	y *= 3;
	x *= 3;

	return { y, x };
}

pair<int, int> nextPos(int y, int x) {
	x++;
	if (x == SIZE) {
		x = 0;
		y++;
	}

	return { y, x };
}

vector<int> candidate(int y, int x) {
	vector<bool> check(10, false);

	for (int i = 0; i < SIZE; i++) {
		int numberX = board[y][i];
		int numberY = board[i][x];
		
		check[numberX] = true;
		check[numberY] = true;
	}

	pair<int, int> start = findStart(y, x);
	for (int i = start.first; i < start.first + 3; i++) {
		for (int j = start.second; j < start.second + 3; j++) {
			int number = board[i][j];

			check[number] = true;
		}
	}

	vector<int> results;
	for (int i = 1; i <= 9; i++) {
		if (!check[i]) {
			results.push_back(i);
		}
	}
	return results;
}

void print() {
	for (int y = 0; y < SIZE; y++) {
		for (int x = 0; x < SIZE; x++) {
			cout << board[y][x];
		}
		cout << '\n';
	}
	cout << '\n';
}

bool solve(int y, int x) {
	if (y == SIZE) {
		print();

		return true;
	}
	if (board[y][x] != 0) {
		pair<int, int> next = nextPos(y, x);
		
		bool result = solve(next.first, next.second);
		if (result) {
			return true;
		}
		return false;
	}

	vector<int> cand = candidate(y, x);
	for (int c : cand) {
		board[y][x] = c;
		pair<int, int> next = nextPos(y, x);
		bool result = solve(next.first, next.second);
		if (result) {
			return true;
		}
		board[y][x] = 0;
	}
	return false;
}

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

	input();
	solve(0, 0);

	return 0;
}