[백준알고리즘] 2580번: 스도쿠 -C++

[백준알고리즘] 2580번: 스도쿠 -C++

2580번: 스도쿠 (acmicpc.net)

2580번: 스도쿠

스도쿠 문제 또한 대표적인 백트래킹 문제 중 하나다. 그만큼 유명하고, 비슷한 문제도 많이 있다. 그럼에도 정답 비율이 30%가 안 되는 것은 그만큼 처음 풀기에도 어려운 문제라는 것 같다.

 

예전에 이 문제를 Python3 (PyPy3)로 풀었다. 두 번 풀었었고, 해당 코드들을 모두 블로그에 쓴 적이 있다.

[백준알고리즘] 2580번: 스도쿠 -Python (tistory.com)

[백준알고리즘] 2580번: 스도쿠 -Python

 

설명도 써놓기도 했는데 그냥 그때 썼던 내용은 놔두고 여기에 간단하게 다시 정리해야겠다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

스도쿠 게임판의 크기는 \( 9 \times 9 \)로 고정되어있다. 그리고, 빈칸은 \( 0 \)으로 두고 스도쿠 판의 상태를 입력받는다.

 

이때, 빈 칸을 채우기만 하는 것이 목적이기 때문에 빈칸만 모아두는 vector를 이용해서 위치를 저장한다. 빈 칸의 위치를 따로 저장해주는 이유는 이렇게 바로 빈칸에 접근해야 DFS를 시도하기 쉬워지기 때문이다.

만약 따로 저장하지 않는다면, 일일이 지나가서 새로운 빈 칸에 여러 가지 수를 시도하고 나아가야 한다. 그리고 가지치기(Prunning) 등으로 인해 진행이 어렵다면 다시 이전 빈 칸으로 이동해야 한다. 하지만, 이것을 기록하지 않는다거나, 재귀 호출로 DFS를 적용하지 않는다면 이것 역시 어려움이 있다.

 

그러니까 아무튼 빈 칸의 위치를 vector로 저장했다.

 

이후, 스도쿠 판에서 하나의 빈칸의 위치에 \( 1 \)부터 \( 9 \)까지 대입해본다. 여기서 빈칸을 채우는 방식은 스도쿠 게임의 규칙으로 문제에 주어져있다.

 

스도쿠 숫자 채우는 규칙

 

따라서 가로줄과 세로줄에 넣으려는 값이 있는지 확인하고, \( 3 \times 3 \) 크기의 칸에 넣으려는 값이 있는지 확인한다. 만약 있다면, 해당 값은 해당 빈칸에 위치할 수 없다.

 

모든 값을 넣을 수 없다면, 이전 빈 칸의 위치로 이동해서 값을 변경하는 전형적인 DFS 방식을 수행하면 된다.

 

결과는 여러 개가 존재한다면, 하나만 출력하면 된다고 주어졌기 때문에 모든 빈칸을 적절히 채울 수 있는 경우가 생긴다면 DFS를 종료하고 그대로 출력시켜주면 된다.

 

아래는 해당 로직으로 푼 C++ 코드다. DFS 과정을 수행하는 것이 fillBlanks 함수고, 각 빈 칸에 주어진 수를 입력할 수 있는지 확인하는 것이 canWriteNumber 함수다.

#include <iostream>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

bool canWriteNumber(std::vector<std::vector<int>>& sudoku, int x, int y, int num)
{
	// 가로축 + 세로축
	for (int i = 0; i < 9; i++)
	{
		if (num == sudoku[i][x])
			return false;
		if (num == sudoku[y][i])
			return false;
	}

	// 3x3 블럭
	int sx = 3 * (x / 3);
	int sy = 3 * (y / 3);

	for (int dx = 0; dx < 3; dx++)
		for (int dy = 0; dy < 3; dy++)
			if (num == sudoku[sy + dy][sx + dx])
				return false;

	return true;
}

bool fillBlanks(std::vector<std::vector<int>>& sudoku, 
		std::vector<std::pair<int, int>>& blank, int blankIndex)
{
	if (blankIndex == blank.size())
		return true;

	int x = blank[blankIndex].first;
	int y = blank[blankIndex].second;

	for (int d = 1; d <= 9; d++)
	{
		if (!canWriteNumber(sudoku, x, y, d))
			continue;

		sudoku[y][x] = d;
		if (fillBlanks(sudoku, blank, blankIndex + 1))
			return true;
		sudoku[y][x] = 0;
	}

	return false;
}

void solve(void)
{
	std::vector<std::vector<int>> sudoku(9, std::vector<int>(9, 0));
	std::vector<std::pair<int, int>> blank;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
		{
			std::cin >> sudoku[i][j];

			if (0 == sudoku[i][j])
				blank.push_back(std::make_pair(j, i));
		}

	fillBlanks(sudoku, blank, 0);

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
			std::cout << sudoku[i][j] << ' ';

		std::cout << '\n';
	}
}