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

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

2239번: 스도쿠

공간(3X3), 행, 열에 어떤 숫자가 있는지 체크하여 백트래킹을 이용해 문제를 해결했다

 

코드

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

int area[10][10]; //[공간][숫자] = (해당 공간에 해당 숫자가 있을때 : 1, 없을때 : 0)
int row[10][10]; //[행][숫자] = (해당 행에 해당 숫자가 있을때 : 1, 없을때 : 0)
int col[10][10]; //[열][숫자] = (해당 열에 해당 숫자가 있을때 : 1, 없을때 : 0)
int board[10][10];

void Pre()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
		{
			area[i][j] = 0;
			row[i][j] = 0;
			col[i][j] = 0;
		}
}

int FindArea(pair<int, int> point)
{
	int ret;

	if (point.first >= 1 && point.first <= 3)
	{
		if (point.second >= 1 && point.second <= 3)
		{
			ret = 1;
		}

		else if (point.second >= 4 && point.second <= 6)
		{
			ret = 2;
		}

		else if (point.second >= 7 && point.second <= 9)
		{
			ret = 3;
		}
	}

	else if (point.first >= 4 && point.first <= 6)
	{
		if (point.second >= 1 && point.second <= 3)
		{
			ret = 4;
		}

		else if (point.second >= 4 && point.second <= 6)
		{
			ret = 5;
		}

		else if (point.second >= 7 && point.second <= 9)
		{
			ret = 6;
		}
	}

	else if (point.first >= 7 && point.first <= 9)
	{
		if (point.second >= 1 && point.second <= 3)
		{
			ret = 7;
		}

		else if (point.second >= 4 && point.second <= 6)
		{
			ret = 8;
		}

		else if (point.second >= 7 && point.second <= 9)
		{
			ret = 9;
		}
	}

	return ret;
}

bool Solve()
{
	pair<int, int> point = make_pair(-1, -1);

	for (int i = 1; i <= 9; i++)
	{
		for (int j = 1; j <= 9; j++)
		{
			if (board[i][j] == 0)
			{
				point = make_pair(i, j);
				break;
			}
		}

		if (point.first != -1)
			break;
	}

	//모든 칸이 다 채워 졌을때
	if (point.first == -1)
	{
		return true;
	}

	
	int this_area = FindArea(point);

	//point칸을 채울 수 있는 수 중에서 가장 작을 수 부터 채워 본다
	for (int i = 1; i <= 9; i++)
	{
		if (area[this_area][i] == 1)
			continue;

		if (row[point.first][i] == 1)
			continue;

		if (col[point.second][i] == 1)
			continue;

		//point위치에 i숫자를 넣어본다
		board[point.first][point.second] = i;
		area[this_area][i] = 1;
		row[point.first][i] = 1;
		col[point.second][i] = 1;

		bool ret = Solve();

		//point위치에 i숫자를 넣어서 전체 칸이 채워지는 경우가 있을때
		if (ret == true)
			return true;

		//point위치에 i숫자 넣은거 뺴기
		board[point.first][point.second] = 0;
		area[this_area][i] = 0;
		row[point.first][i] = 0;
		col[point.second][i] = 0;
	}

	return false;
}

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

	Pre();

	for (int i = 1; i <= 9; i++)
	{
		string input;
		cin >> input;

		for (int j = 1; j <= 9; j++)
		{
			int number = input[j - 1] - '0';

			board[i][j] = number;

			int this_area = FindArea(make_pair(i, j));
			area[this_area][number] = 1;
			row[i][number] = 1;
			col[j][number] = 1;
		}
	}

	Solve();

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


	return 0;
}