Baekjoon
[#2580] 스도쿠
강람이
2020. 3. 10. 20:01
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <stdio.h>
#define SIZE 9
using namespace std;
vector<vector<int>> board(SIZE, vector<int>(SIZE, 0));
bool promising(int row, int col, int k) {
//board[row][col]에 k가 들어갈 수 있으면 true, 없으면 flase return
//가로 확인
for (int i = 0; i < SIZE; i++) {
if (board[row][i] == k)
return false;
}
//세로 확인
for (int i = 0; i < SIZE; i++) {
if (board[i][col] == k)
return false;
}
//3*3 확인
for (int i = row - (row % 3); i < row + (3 - (row % 3)); i++) {
for (int j = col - (col % 3); j < col + (3 - (col % 3)); j++) {
if (board[i][j] == k)
return false;
}
}
return true;
}
void recursive(int count) {
if (count == 81) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
exit(0);
}
int row = count / SIZE;
int col = count % SIZE;
if (board[row][col] == 0) {
for (int i = 1; i <= 9; i++) {
if(promising(row,col,i)){
board[row][col] = i;
recursive(count + 1);
board[row][col] = 0;
}
}
}
else
recursive(count + 1);
}
int main() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
scanf("%d", &board[i][j]);
}
}
recursive(0);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
처음 코드. 시간 더 짧게 풀 수도 있을거같아서 찾아보고 쓴 두번째 코드는
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <stdio.h>
#define SIZE 9
using namespace std;
vector<vector<int>> board(SIZE, vector<int>(SIZE, 0));
vector<vector<bool>> rowVec(SIZE, vector<bool>(SIZE + 1, false)); //rowVec[i][num]은 i번째 행에 num이 있는지 없는지
vector<vector<bool>> colVec(SIZE, vector<bool>(SIZE + 1, false)); //colVec[i][num]은 i번째 열에 num이 있는지 없는지
vector<vector<bool>> squareVec(SIZE, vector<bool>(SIZE + 1, false));
//squareVec[i][num]은 i번째 3*3에 num이 있는지
//3*3 순서는
// 0 1 2
// 3 4 5
// 6 7 8
void recursive(int count) {
if (count == 81) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
exit(0);
}
int row = count / SIZE;
int col = count % SIZE;
if (board[row][col] == 0) {
int tempRow = (row - (row % 3)) / 3;
int tempCol = col - (col % 3);
for (int i = 1; i <= 9; i++) {
if (rowVec[row][i] == false && colVec[col][i] == false && squareVec[tempRow + tempCol][i] == false) {
board[row][col] = i;
rowVec[row][i] = true;
colVec[col][i] = true;
squareVec[tempRow + tempCol][i] = true;
recursive(count + 1);
board[row][col] = 0;
rowVec[row][i] = false;
colVec[col][i] = false;
squareVec[tempRow + tempCol][i] = false;
}
}
}
else
recursive(count + 1);
}
int main() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
scanf("%d", &board[i][j]);
if (board[i][j] != 0) {
rowVec[i][board[i][j]] = true;
colVec[j][board[i][j]] = true;
int tempRow = (i - (i % 3)) / 3;
int tempCol = j - (j % 3);
squareVec[tempRow + tempCol][board[i][j]] = true;
}
}
}
recursive(0);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
N-Queen 문제에서도 그렇고 스도쿠 문제에서도 그렇고 이차원 행렬을 맵으로 쓰는 경우 각 행과 열에 대한 정보 알려주는 벡터를 만들고 이를 promising 함수에 이용하면 시간을 줄일 수 있는것 같다.
답이 여러개인 경우 하나만 출력하는 문제에서는 답 나오면 출력하고 바로 exit(0)으로 프로그램 끝내기