문제 출처

1. 문제설명

  • 스도쿠는 9x9 보드판에 숫자를 채우는 게임이다.
  • 규칙은 간단하다.
    • 가로 또는 세로축에 1~9의 숫자는 중복될 수 없다.
    • 3x3 크기의 사각형 안에도 1~9까지의 숫자가 중복될 수 없다.
  • 빈칸이 0으로 채워져있을 때 완전한 스도쿠를 구하라.



2. 알고리즘 설계

  • DFS로 값을 채워나가되,
  • 언급한 스도쿠 조건에 맞는지 검사하면 된다.



3. 로직

  • 가로 또는 세로 방향에 같은 값이 있는지 체크하는 건 간단하니 생략
  • 3x3 크기의 사각형은 (x, y)라는 현재 좌표가 주어질 때
    • 이 값을 3으로 나누고 3을 곱하면
    • 몇 번째 사각형에 속하는 지 알 수 있다.
    • int 나눗셈의 소수점이 버려지는 걸 이용하였다.



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

bool flag = false;
int sudoku[9][9];
vector<pii> v;

bool check(pair<int, int> p)
{
	int square_x = p.first / 3 * 3;
	int square_y = p.second / 3 * 3;

	for (int i = 0; i < 9; i++)
	{
		if (sudoku[p.first][i] == sudoku[p.first][p.second] && i != p.second)
			return false;
		if (sudoku[i][p.second] == sudoku[p.first][p.second] && i != p.first)
			return false;
	}

	for (int i = square_x; i < square_x + 3; i++)
		for (int j = square_y; j < square_y + 3; j++)
			if (sudoku[i][j] == sudoku[p.first][p.second])
				if (i != p.first && j != p.second)
					return false;

	return true;
}

void dfs(int n) {
	if (n == v.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << sudoku[i][j] << ' ';
			cout << '\n';
		}
		flag = true;
		return;
	}

	for (int i = 1; i <= 9; i++) {
		sudoku[v[n].first][v[n].second] = i;
		
		if (check(v[n])) dfs(n + 1);
		if (flag) return;
	}

	sudoku[v[n].first][v[n].second] = 0;
	return;
}

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

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			cin >> sudoku[i][j];
			if (sudoku[i][j] == 0)
				v.push_back({ i,j });
		}

	dfs(0);
	return 0;
}



5. 소감

  • 이 문제의 약간 헷갈릴 수 있는 부분은
  • 전부 빈칸인 스도쿠가 주어질 수 있다는 것이다.
  • 예제만 보고, 중간 중간 몇 개만 비워져있겠구나 생각하면 안된다!