알고리즘 :: 백준 :: Bruteforce :: 2580 :: 스도쿠

문제

문제접근

문제 이해

• 스도쿠는 $9 \times 9$ 배열, 즉 81칸으로 이뤄져있습니다.
• 0번째 칸부터 재귀를 돌면서 0이 들어있는 칸에 대해서는 임의의 숫자를 넣습니다.
  • 숫자를 넣을 때는 가로와 세로 그리고 포함된 그룹을 검사해서 적합한 숫자를 찾습니다.
• 1~9 까지 수는 각 행과 열 그리고 그룹에 단 하나만 존재해야 합니다.
  • 저는 코드상에서 매 재귀마다 가로, 세로 그리고 그룹을 검사하는 방법을 사용했습니다.
    • 이 방법은 후술할 방법보다 더 오랜 시간이 걸리는 방법입니다.
    • 그나마 조금 더 효율적으로 하기 위해, 저는 스도쿠를 입력받을 때 0의 자리를 따로 저장해서 재귀 호출 횟수를 줄이는 방법을 사용했습니다.
  • 혹은 전역변수에 bool타입 배열 3개를 만들어서 검사하는 방법도 있습니다.
    • row[i][num]: i번째 행에 num이라는 수가 있다면 true.
    • col[i][num]: i번째 열에 num이라는 수가 있다면 true.
    • group[i][num]: i번째 그룹에 num이라는 수가 있다면 true.
• (y, x) 라는 좌표는 (y / 3) * 3 + x / 3 번째 그룹에 속해있습니다.
  그 그룹의 시작점 좌표는 ((y / 3) * 3), (x / 3 ) * 3)입니다.

코드

#include <iostream>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

struct Pos { int y, x; };
int emptyCnt, map[9][9];
Pos empty[81];

void go(int cnt) {
	if (cnt == emptyCnt) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j)
				cout << map[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}
	bool table[10] = {false, };
	int cy = empty[cnt].y, cx = empty[cnt].x;	// curY, curX
	int gy = (cy / 3) * 3, gx = (cx / 3) * 3;	// groupY, groupX
	// Check row and col from (cy, cx)
	for (int i = 0; i < 9; ++i) {
		if (!table[map[cy][i]]) table[map[cy][i]] = true;
		if (!table[map[i][cx]]) table[map[i][cx]] = true;
	}
	// Check the group which (cy, cx) included
	for (int i = gy; i < gy + 3; ++i)
		for (int j = gx; j < gx + 3; ++j)
			if (!table[map[i][j]]) table[map[i][j]] = true;
	for (int i = 1; i <= 9; ++i) {
		if (table[i]) continue;
		map[cy][cx] = i;	// Check
		go(cnt + 1);	// Go
		map[cy][cx] = 0;	// Uncheck
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	for (int i = 0; i < 9; ++i)
		for (int j = 0; j < 9; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 0) empty[emptyCnt++] = {i, j};
		}
	go(0);
}

재풀이 코드

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

int map[9][9];
bool row[9][10], col[9][10], group[9][10];
vector<pair<int, int>> emptySpace;

int getGroupNum(int y, int x) {
	return (y / 3) * 3 + (x / 3);
}

void solve(int cnt) {
	if (cnt == emptySpace.size()) {
		for (int y = 0; y < 9; ++y) {
			for (int x = 0; x < 9; ++x)
				cout << map[y][x] << ' ';
			cout << '\n';
		}
		exit(0);
	}
	for (int i = 1; i <= 9; ++i) {
		int y = emptySpace[cnt].first, x = emptySpace[cnt].second;
		if (row[y][i] || col[x][i] || group[getGroupNum(y, x)][i]) continue;
		map[y][x] = i;
        	row[y][i] = col[x][i] = group[getGroupNum(y, x)][i] = true;
		solve(cnt + 1);
        	row[y][i] = col[x][i] = group[getGroupNum(y, x)][i] = false;
        	map[y][x] = 0;
	}
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    for (int y = 0; y < 9; ++y)
    	for (int x = 0; x < 9; ++x) {
    		cin >> map[y][x];
    		row[y][map[y][x]] = col[x][map[y][x]] = group[getGroupNum(y, x)][map[y][x]] = true;
    		if (map[y][x] == 0) emptySpace.push_back({y, x});
    	}
    solve(0);
}

결과

재풀이 결과