https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net

풀이는 여기로 https://kyj0032.tistory.com/107
백준 g4 2239 스도쿠 c++
https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타
kyj0032.tistory.com
전체 코드
/*boj g4 2580 스도쿠*/
#include <iostream>
#define MAXN 105
using namespace std;
int N;
string str[10];
int board[9][9];
bool isEnd() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) return false;
}
}
return true;
}
bool isInHorizontal(int x, int y, int k) {
for (int j = 0; j < 9; j++) {
if (board[x][j] == k) return true;
}
return false;
}
bool isInVertical(int x, int y, int k) {
for (int i = 0; i < 9; i++) {
if (board[i][y] == k) return true;
}
return false;
}
bool isInBox(int x, int y, int k) {
// 0 1 2 / 3 4 5 / 6 7 8
int xCond = x / 3;
int yCond = y / 3;
for (int i = 3 * (x / 3); i < 3 * (x / 3) + 3; i++) {
for (int j = 3 * (y / 3); j < 3 * (y / 3) + 3; j++) {
if (board[i][j] == k) return true;
}
}
return false;
}
void print() {
// cout << "================\n";
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << board[i][j] << " ";
}
cout << "\n";
}
}
void dfs(int x, int y) {
// print();
// if () x, y가 끝이면?
if (isEnd()) {
print();
exit(0);
}
for (int i = x; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != 0) continue;
for (int k = 1; k <= 9; k++) {
if (isInHorizontal(i, j, k)) continue;
if (isInVertical(i, j, k)) continue;
if (isInBox(i, j, k)) continue;
board[i][j] = k;
dfs(i, j);
board[i][j] = 0;
}
return;
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> board[i][j];
}
}
dfs(0, 0);
}
'알고리즘' 카테고리의 다른 글
백준 g1 21611 마법사 상어와 블리자드 c++ (0) | 2024.04.12 |
---|---|
백준 g2 19238 스타트 택시 c++ (0) | 2024.04.11 |
백준 g4 2239 스도쿠 c++ (0) | 2024.03.22 |
백준 g4 4803 트리 c++ (0) | 2024.03.21 |
백준 g5 2166 다각형의 면적 c++ (0) | 2024.03.20 |