백준 2239번 스도쿠 C++

출처 : https://www.acmicpc.net/problem/2239

 

행과 열의 정보를 이용해서 해당 열, 행, 속해있는 구역에 있는 숫자들을 unordered_set으로 관리하면서 들어갈 수 있는 숫자가 있다면 백트래킹을 이용해서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

vector<unordered_set<int>> vr(10);
vector<unordered_set<int>> vc(10);
vector<unordered_set<int>> vs(10);

vector<vector<int>> board(10, vector<int>(10, 0));

int GetSector(int row, int col) {
	int ret, r, c;
	if (row <= 3) {
		r = 0;
	}
	else if (row <= 6) {
		r = 1;
	}
	else {
		r = 2;
	}

	if (col <= 3) {
		c = 1;
	}
	else if (col <= 6) {
		c = 2;
	}
	else {
		c = 3;
	}
	ret = r * 3 + c;
	return ret;
}

void FillVs(int row, int col, int value) {
	vr[row].insert(value);
	vc[col].insert(value);
	vs[GetSector(row, col)].insert(value);
}

void BT(int row, int col) {
	if (row == 10) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				cout << board[i][j];
			}
			cout << "\n";
		}
		exit(0);
	}
	if (board[row][col] != 0) {
		if (col == 9) {
			BT(row + 1, 1);
		}
		else {
			BT(row, col + 1);
		}
	}
	else {
		for (int i = 1; i <= 9; i++) {
			if (vr[row].find(i) == vr[row].end() &&
				vc[col].find(i) == vc[col].end() &&
				vs[GetSector(row, col)].find(i) == vs[GetSector(row, col)].end()) {
				vr[row].insert(i);
				vc[col].insert(i);
				vs[GetSector(row, col)].insert(i);
				board[row][col] = i;
				if (col == 9) {
					BT(row + 1, 1);
				}
				else {
					BT(row, col + 1);
				}
				vr[row].erase(i);
				vc[col].erase(i);
				vs[GetSector(row, col)].erase(i);
				board[row][col] = 0;
			}
		}
	}
}

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

	string str;
	for (int i = 1; i <= 9; i++) {
		cin >> str;
		str = " " + str;
		for (int j = 1; j <= 9; j++) {
			board[i][j] = str[j] - '0';
			FillVs(i, j, board[i][j]);
		}
	}
	BT(1, 1);
};