[백준] 2580번 - 스도쿠
[링크] https://www.acmicpc.net/problem/2580
💎 문제 조건과 설명
문제 조건과 설명은 위의 링크를 참조 부탁드립니다.
🚀 생각한 아이디어
DFS와 백트래킹을 결합하여 푸는 문제였습니다.
먼저 특정 칸에 숫자를 놓아 보고, 그 칸을 기준으로 행(ㅡ), 열(|), 단위 정사각형(3x3) 구역 이렇게 3가지에 대해서 모두 검사합니다. 검사할 때에는 각 구역에 숫자가 한 개씩만 존재하는지 확인합니다.
만약 3가지 검사 중에서 하나라도 통과하지 못할 경우, 놓은 숫자를 다시 0으로 만든 다음 back 하여 이전 단계에서 새로운 숫자를 다시 놓아 보면서 계속 진행해 나가면 됩니다.
그리고 (8,8)에 도착했을 경우, 모든 칸이 채워졌는지 확인합니다. 채워졌을 경우, 9x9 칸을 출력하며 프로그램을 즉시 종료시켜야 합니다. 만약 계속 통과되지 않으시다면 이 부분을 확인해 보세요.
c++의 경우 exit(0)을 사용하여 프로그램을 즉시 종료할 수 있습니다.
- (참고) 아래 소스코드에서는 특정 칸이 어떤 단위 정사각형에 속하는지 squNum 함수를 작성하여 만들었는데, 사실 더 간단하게 구할 수도 있습니다.
- (a, b) 가 속하는 단위 정사각형의 맨 첫번째 칸의 위치는
(a/3 * 3, b/3 * 3)으로 쉽게 구할 수 있습니다. 이 부분을 다르게 작성해서 실행 시간이 얼마나 다른지 확인하는 것도 좋을 것 같습니다!
- 소스코드 : 주석으로 최대한 자세히 써 놓았으니 참고해 주세요!
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_set>
using namespace std;
int board[9][9];
// 가로 행 검사하는 함수
bool rowCheck(int rowNum) {
int cnt[10];
for (int i = 0; i < 10; i++)
cnt[i] = 0;
for (int i = 0; i < 9; i++) {
if (board[rowNum][i] != 0)
cnt[board[rowNum][i]] += 1;
if (cnt[board[rowNum][i]] >= 2) return false;
}
return true;
}
// 세로 열 검사하는 함수
bool colCheck(int colNum) {
int cnt[10];
for (int i = 0; i < 10; i++)
cnt[i] = 0;
for (int i = 0; i < 9; i++) {
if (board[i][colNum] != 0)
cnt[board[i][colNum]] += 1;
if (cnt[board[i][colNum]] >= 2) return false;
}
return true;
}
// 특정 칸이 몇 번째 단위정사각형에 포함되는지 반환
pair<int,int> squNum(int rowNum, int colNum) {
if (rowNum >= 0 && rowNum <= 2) {
if (0 <= colNum && colNum <= 2)
return { 0,0 };
else if (3 <= colNum && colNum <= 5)
return { 0,3 };
else if (6 <= colNum && colNum <= 8)
return { 0,6 };
}
else if (rowNum >= 3 && rowNum <= 5) {
if (0 <= colNum && colNum <= 2)
return { 3,0 };
else if (3 <= colNum && colNum <= 5)
return { 3,3 };
else if (6 <= colNum && colNum <= 8)
return { 3,6 };
}
else if (rowNum >= 6 && rowNum <= 8) {
if (0 <= colNum && colNum <= 2)
return { 6,0 };
else if (3 <= colNum && colNum <= 5)
return { 6,3 };
else if (6 <= colNum && colNum <= 8)
return { 6,6 };
}
}
// 특정 칸의 단위 정사각형 9칸을 검사하는 함수
bool squCheck(int rowNum, int colNum) {
int cnt[10];
for (int i = 0; i < 10; i++)
cnt[i] = 0;
pair<int, int> square_num = squNum(rowNum, colNum);
int row = square_num.first;
int col = square_num.second;
for (int i = row; i < row + 3; i++) {
for (int j = col; j < col + 3; j++) {
if(board[i][j] != 0)
cnt[board[i][j]] += 1;
if (cnt[board[i][j]] >= 2) return false;
}
}
return true;
}
void simulation(int row, int col) {
// 칸을 다 채웠을 경우 출력 후 종료
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// 빈 칸에 대해서 검사
if (board[i][j] == 0) {
//1부터 9까지 빈 칸에 대입해 본다.
for (int k = 1; k <= 9; k++) {
board[i][j] = k;
// 모든 체크에 통과 시
if (rowCheck(i) && colCheck(j) && squCheck(i, j)) {
simulation(i, j);
}
board[i][j] = 0;
}
return;
}
if (i == 8 && j == 8) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) {
return;
}
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << board[i][j] << ' ';
}
cout << '\n';
}
exit(0);
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> board[i][j];
}
}
simulation(0,0);
return 0;
}