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

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

문제

---

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

---

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

 

출력

---

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

제한

---

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++17: 180ms
  • Java 15: 528ms
  • PyPy3: 2064ms

 

문제 풀이

---

백트래킹을 이용한 구현 문제.

문자열로 입력받아 int 타입 2차원 배열에 숫자들을 저장한다. 아직 숫자가 채워지지 않아 0인 칸들을 따로 벡터에 저장하여 백트래킹 탐색 할 수 있도록 한다. 백트래킹 함수의 깊이는 칸을 채울 벡터 인덱스 값이 되며, 백트래킹 함수의 깊이가 벡터의 크기만큼이라면 모든 칸이 채워진 것이 된다.

현재 함수의 깊이에 해당하는 벡터의 인덱스의 정보를 가져와 채울 칸을 1~9까지 넣을 수 있는지 확인한다. 만약 특정 숫자를 채울 수 있다면 해당 숫자로 칸을 채우고, 다음 칸을 채울 수 있도록 깊이를 1 증가시켜 백트래킹 함수를 호출한다. 특정 숫자를 채울 수 있는 조건은 스도쿠 규칙과 같이 행, 열, 3*3 정사각형에 모두 그 숫자가 있지 않아야 한다.

백트래킹 함수가 호출되고 나면 백트래킹 기본 예제에서 방문한 index를 false 처리하듯, 다른 숫자를 채울 수 있도록 해당 위치의 칸을 0으로 변경해준다.

 

아래는 코드.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int** arr;
vector<pair<int, int>> shouldFill;
bool isMade;

bool canFillRowCol(int row, int col, int checkNum)
{
	bool canFill = true;
	for (int i = 0; i < 9; i++)
	{
		if (arr[i][col] == checkNum)
		{
			canFill = false;
			return canFill;
		}
		if (arr[row][i] == checkNum)
		{
			canFill = false;
			return canFill;
		}
	}
	return canFill;
}

bool canFill3x3Square(int row, int col, int checkNum)
{
	int startX = row / 3 * 3;
	int startY = col / 3 * 3;
	bool canFill = true;
	for (int i = startX; i < startX + 3; i++)
	{
		for (int j = startY; j < startY + 3; j++)
		{
			if (arr[i][j] == checkNum)
			{
				return false;
			}
		}
	}
	return true;
}

void backTracking(int depth)
{
	if (depth == shouldFill.size())
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				cout << arr[i][j];
			}
			cout << "\n";
		}
		isMade = true;
		return;
	}
	else
	{
		if (isMade == true)
		{
			return;
		}
		int row = shouldFill.at(depth).first;
		int col = shouldFill.at(depth).second;
		bool canFill = true;
		for (int num = 1; num <= 9; num++)
		{
			canFill = canFillRowCol(row, col, num) && canFill3x3Square(row, col, num);
			if (canFill == true)
			{
				arr[row][col] = num;
				backTracking(depth + 1);
				arr[row][col] = 0;
			}
		}
	}
}

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

	string str;
	arr = new int*[9];
	for (int i = 0; i < 9; i++)
	{
		arr[i] = new int[9];
		cin >> str;
		for (int j = 0; j < 9; j++)
		{
			arr[i][j] = str.at(j) - 48;
			if (str.at(j) == '0')
			{
				shouldFill.push_back(pair(i, j));
			}
		}
	}
	backTracking(0);
	return 0;
}