2580 - 스도쿠

문제 : https://www.acmicpc.net/problem/2580

2580번: 스도쿠

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 9;
int sudoku[MAX][MAX];
bool row[MAX][MAX + 1]; //열, 1~9
bool col[MAX][MAX + 1]; //행, 1~9
bool square[MAX][MAX + 1]; //3*3 박스 idx, 1~9

int change2SquareIdx(int y, int x) // small square
{
	return (y / 3) * 3 + x / 3;
}

void DFS(int cnt)
{
	if (cnt == 81) {//Sudoku는 총 81칸
		for (int i = 0; i < MAX; i++) {
			for (int j = 0; j < MAX; j++)
				cout << sudoku[i][j] << " ";
			cout << endl;
		}
		exit(0); //답을 하나만 출력
	}

	int y = cnt / 9;
	int x = cnt % 9;
	if (sudoku[y][x]) //칸이 채워져있으면
		DFS(cnt + 1);
	else { //채워져있지 않았고	
		for (int k = 1; k <= MAX; k++) {
			//sudoku 규칙에 적합하면 채우고 본다
			if (!col[x][k] && !row[y][k] && !square[change2SquareIdx(y, x)][k]) {
				sudoku[y][x] = k;
				col[x][k] = true;
				row[y][k] = true;
				square[change2SquareIdx(y, x)][k] = true;
				DFS(cnt + 1);
				sudoku[y][x] = 0;
				col[x][k] = false;
				row[y][k] = false;
				square[change2SquareIdx(y, x)][k] = false;
			}
		}
	}
}

int main(void)
{
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			cin >> sudoku[i][j];
			if (sudoku[i][j]) {
				col[j][sudoku[i][j]] = true;							// j열에 sudoku[i][j] 체크
				row[i][sudoku[i][j]] = true;							// i행에 sudoku[i][j] 체크 
				square[change2SquareIdx(i, j)][sudoku[i][j]] = true;	// 작은 사각형의 체크
			}
		}
	}

	DFS(0); //sudoku는 81칸
	return 0;
}

참고 : https://jaimemin.tistory.com/664

백준 2580번 스도쿠

• 재귀함수를 이용해 조건에 맞을 경우, 순차적으로 스도쿠에 수를 채우는문제였습니다.
• 입력을 받을때가 중요합니다.
• 예를 들어 아래와 같이 처리합니다.
• col[j][sudoku[i][j]] = true; // j열에 sudoku[i][j] 체크

row[i][sudoku[i][j]] = true; // i행에 sudoku[i][j] 체크

square[change2SquareIdx(i, j)][sudoku[i][j]] = true; // 작은 사각형의 체크

한 입력이 들어올때, 이것은 9*9 스도쿠에서의 한 열과 한 행에 두 가지 경우에 대해서 모두 공통적으로 입력되는 것입니다.

그렇기 때문에 sudoku[i][j] 입력이 있을때, 이 수를 col[j][sudoku[i][j], row[i][sudoku[i][j]]에 대해서 true, false 처리해줍니다.

• 또 중요한 것이 작은 사각형 3*3을 처리하는 것입니다. 이것은 int change2SquareIdx(int y, int x) 함수로 좌표를 변환해줍니다.

• 이와 비슷한 문제가 있는것으로 복습을 해야겠네요.