이 문제는 brute force 문제이다.
스도쿠 문제를 풀어봤다면 규칙을 정확히 알고 있을 것이다.
1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
dfs로 풀었다.
1. 숫자를 입력받을 때 가로줄, 세로줄, 3x3 정사각형에 쓰여진 숫자에 대한 기록을 한다.
3x3 정사각형을 위와 같이 나누고 숫자 각각에 대한 기록을 하기 위해서는
sudoku[y][x] 라고 가정했을 때,
y / 3 * 3 + x / 3 이라는 식을 통해 정사각형을 나눌 수 있다.
sudoku[1][1]일 경우
1 / 3 * 3 + 1 / 3 = 0 * 3 + 0 = 0
sudoku[2][3]일 경우
2 / 3 * 3 + 3 / 3 = 0 * 3 + 1 = 1
가로줄은 row, 세로줄은 column, 3 * 3 정사각형은 square로 배열 변수를 설정하여
숫자의 유무를 설정한다.
for(int i = 0; i < 9; i ++){
for(int j = 0; j < 9; j++){
cin >> sudoku[i][j];
if(sudoku[i][j] != 0){
row[i][sudoku[i][j]] = true;
column[j][sudoku[i][j]] = true;
square[(i/3)*3 + j/3][sudoku[i][j]] = true;
}
}
}
2. count에 따라 x와 y를 구하고,
만일 x, y에 위치한 숫자가 0일 경우,
1부터 9 까지 반복문을 돌렸을 때, row, column, square 에 존재하지 않는 수를 배열에 넣어준다.
그리고 각 배열에 그 수가 있음을 표시한다.
재귀가 끝난 후, 다시 새로운 수에 대한 가지치기를 하기위해
row, column, square에 그 수가 없다고 표시한 후 다시 반복문을 돌게끔 한다.
만일 숫자가 0이 아닐 경우,
다른 인덱스를 방문하기 위해 재귀함수를 호출한다.
int y = count / 9;
int x = count % 9;
if(sudoku[y][x] == 0){
for(int i = 1; i <= 9; i++){
if(!row[y][i]&& !column[x][i] && !square[(y/3)*3 + x/3][i]){
sudoku[y][x] = i;
row[y][i] = true;
column[x][i] = true;
square[(y/3)*3 + x/3][i] = true;
dfs(count + 1);
sudoku[y][x] = 0;
row[y][i] = false;
column[x][i] = false;
square[(y/3)*3 + x/3][i] = false;
}
}
}
else{
dfs(count + 1);
}
}
재귀를 돌다가 count가 81이 되면, print를 하고,
다른 경우의 수를 print하지 않고 재귀를 완전히 나가기 위해
exit(0)을 호출한다.
if(count == 81){
for(int i = 0; i < 9; i ++){
for(int j = 0; j < 9; j++){
cout << sudoku[i][j] << " ";
}
cout << "\n";
}
exit(0);
}
전체적인 코드는 이와 같다.
//스도쿠
#include <iostream>
using namespace std;
int sudoku[10][10];
bool row[10][10];
bool column[10][10];
bool square[10][10];
void dfs(int count){
if(count == 81){
for(int i = 0; i < 9; i ++){
for(int j = 0; j < 9; j++){
cout << sudoku[i][j] << " ";
}
cout << "\n";
}
exit(0);
}
int y = count / 9;
int x = count % 9;
if(sudoku[y][x] == 0){
for(int i = 1; i <= 9; i++){
if(!row[y][i]&& !column[x][i] && !square[(y/3)*3 + x/3][i]){
sudoku[y][x] = i;
row[y][i] = true;
column[x][i] = true;
square[(y/3)*3 + x/3][i] = true;
dfs(count + 1);
sudoku[y][x] = 0;
row[y][i] = false;
column[x][i] = false;
square[(y/3)*3 + x/3][i] = false;
}
}
}
else{
dfs(count + 1);
}
}
int main(void){
for(int i = 0; i < 9; i ++){
for(int j = 0; j < 9; j++){
cin >> sudoku[i][j];
if(sudoku[i][j] != 0){
row[i][sudoku[i][j]] = true;
column[j][sudoku[i][j]] = true;
square[(i/3)*3 + j/3][sudoku[i][j]] = true;
}
}
}
dfs(0);
}
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 로봇 청소기 (0) | 2020.12.22 |
---|---|
[algorithm] 백준 - 구슬탈출(2) (0) | 2020.12.18 |
[algorithm] 백준 - 숨바꼭질 2 (0) | 2020.11.17 |
[algorithm] 백준 - 스타트와 링크 (0) | 2020.11.17 |
[algorithm] 백준 - 단어수학 (0) | 2020.11.14 |