[백준/BOJ] 백준 2580번 : 스도쿠

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

row_check에 [행번호][숫자] = (해당 행에 해당 숫자가 있으면 : 1, 없으면 0), col_check에 [열번호][숫자] = (해당 열에 해당 숫자가 있으면 : 1, 없으면 0), area_check에 [구역번호][숫자] = (해당 구역에 해당 숫자가 있으면 : 1, 없으면 0)를 저장하여 해당 위치에 특정 숫자가 들어갈 수 있는지 판단하는 방법으로 문제를 해결했다.

 

코드

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

int board[9][9];
vector<vector<int>> row_check(9, vector<int>(10, 0)); //[행번호][숫자] = (해당 행에 해당 숫자가 있으면 : 1, 없으면 0)
vector<vector<int>> col_check(9, vector<int>(10, 0)); //[열번호][숫자] = (해당 열에 해당 숫자가 있으면 : 1, 없으면 0)
vector<vector<int>> area_check(9, vector<int>(10, 0)); //[구역번호][숫자] = (해당 구역에 해당 숫자가 있으면 : 1, 없으면 0)
vector<pair<int, int>> point;
int area_number[9][9]; //(위치) = 구역번호

void Pre()
{
	//위치별로 구역번호를 저장
	pair<int, int> start = make_pair(0, 0);
	for (int cnt = 0; cnt < 9; cnt++)
	{
		for (int i = start.first; i < start.first + 3; i++)
		{
			for (int j = start.second; j < start.second + 3; j++)
			{
				area_number[i][j] = cnt;
			}
		}

		start.second += 3;

		if (start.second >= 9)
		{
			start.first += 3;
			start.second = 0;
		}
	}

	//가로, 세로, 구역 체크
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			if (board[i][j] == 0)
				continue;

			row_check[i][board[i][j]] = 1;
			col_check[j][board[i][j]] = 1;
			area_check[area_number[i][j]][board[i][j]] = 1;
		}
	}
}

//index 빈칸을 확인한다
bool Solve(int index)
{
	//끝까지 확인 했을때
	if (index == point.size())
		return true;

	pair<int, int> here = point[index];
	bool ret;
	int this_area_number = area_number[here.first][here.second];

	for (int i = 1; i <= 9; i++)
	{
		//i가 해당 위치에 들어갈 수 있을때
		if (row_check[here.first][i] == 0 && col_check[here.second][i] == 0 && area_check[this_area_number][i] == 0)
		{
			row_check[here.first][i] = 1;
			col_check[here.second][i] = 1;
			area_check[this_area_number][i] = 1;
			board[here.first][here.second] = i;

			ret = Solve(index + 1);

			if (ret == true)
				return ret;

			//원상복구
			row_check[here.first][i] = 0;
			col_check[here.second][i] = 0;
			area_check[this_area_number][i] = 0;
			board[here.first][here.second] = 0;
		}
	}

	return false;
}

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

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			int input;
			cin >> input;

			//빈칸인 경우
			if (input == 0)
				point.push_back(make_pair(i, j));

			board[i][j] = input;
		}
	}

	Pre();
	Solve(0);

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << board[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}