백준 2580번 스도쿠
문제
풀이
- 백트래킹을 이용하여 해결한다.
- 빈칸의 위치를 저장하는 벡터 배열을 만들고 벡터 배열을 모두 채우면 종료시킨다.
- 스도쿠 칸을 채우는 방법이 여러 개라도 한번만 출력하므로 한번 완성시면 종료시킨다.
- DFS 방식으로 문제를 해결하는데 이 때 한 빈칸을 채우고 다음 빈칸을 채우려는데 모든 숫자가 안되는 경우가 발생할 수 있다. 이때는 채우려는 빈칸을 0으로 만들고 이전 빈칸 채우기로 돌아가서 가능한 다른 숫자를 대입하여 다음 빈칸을 채우는 방식으로 채워나간다.
코드
//난이도 : 골드4
#include <iostream>
#include <vector>
using namespace std;
int puzzle[9][9] = { 0 }; //스도쿠 퍼즐 저장 배열
vector<pair<int, int>> blank; //빈 칸 위치 저장 벡터
bool stop = false; //끝남 표시
//pruning 조건
bool is_available(int cur_r, int cur_c) {
for (int r = 0; r < 9; r++) { //같은 행에 같은 숫자가 있으면 탈락, 자기 자신은 패스
if (puzzle[cur_r][cur_c] == puzzle[r][cur_c] && cur_r != r) {
return false;
}
}
for (int c = 0; c < 9; c++) { //같은 열에 같은 숫자가 있으면 탈락, 자기 자신은 패스
if (puzzle[cur_r][cur_c] == puzzle[cur_r][c] && cur_c != c) {
return false;
}
}
//같은 박스에 같은 숫자가 있으면 탈락, 자기 자신은 패스
int box_r = cur_r / 3;
int box_c = cur_c / 3;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (puzzle[cur_r][cur_c] == puzzle[box_r * 3 + r][box_c * 3 + c] && cur_r != box_r*3+r && cur_c != box_c*3+c) {
return false;
}
}
}
//중간에 걸리지 않은 경우 참
return true;
}
void solve(int size, int cur_size) {
if (size == cur_size) { //판을 다 채운 경우
stop = true; //끝남 표시
// 정답 출력
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
cout << puzzle[r][c] << " ";
}
cout << '\n';
}
return;
}
// 현재 위치 r, c 저장
int cur_r = blank[cur_size].first;
int cur_c = blank[cur_size].second;
for (int i = 1; i <= 9; i++) {
puzzle[cur_r][cur_c] = i; //1부터 9까지 대입
if (is_available(cur_r, cur_c)) { //참이면 다음 빈칸 채우기
solve(size, cur_size + 1);
}
//빈칸 채우기가 끝나거나 이전 숫자 때문에 다른 빈칸에 어떤 수도 들어갈 수 없는경우
if (stop == true) { //빈칸 채우기가 끝난 경우
return;
}
puzzle[cur_r][cur_c] = 0; //빈칸을 0으로 만들고 이전에 들어갈 수 있는 다른 숫자를 찾는다.
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//입력
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
cin >> puzzle[r][c];
if (puzzle[r][c] == 0) {
blank.push_back(make_pair(r, c));
}
}
}
solve(blank.size(), 0);
return 0;
}
Author And Source
이 문제에 관하여(백준 2580번 스도쿠), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@jsleeg98/백준-2580번-스도쿠
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
//난이도 : 골드4
#include <iostream>
#include <vector>
using namespace std;
int puzzle[9][9] = { 0 }; //스도쿠 퍼즐 저장 배열
vector<pair<int, int>> blank; //빈 칸 위치 저장 벡터
bool stop = false; //끝남 표시
//pruning 조건
bool is_available(int cur_r, int cur_c) {
for (int r = 0; r < 9; r++) { //같은 행에 같은 숫자가 있으면 탈락, 자기 자신은 패스
if (puzzle[cur_r][cur_c] == puzzle[r][cur_c] && cur_r != r) {
return false;
}
}
for (int c = 0; c < 9; c++) { //같은 열에 같은 숫자가 있으면 탈락, 자기 자신은 패스
if (puzzle[cur_r][cur_c] == puzzle[cur_r][c] && cur_c != c) {
return false;
}
}
//같은 박스에 같은 숫자가 있으면 탈락, 자기 자신은 패스
int box_r = cur_r / 3;
int box_c = cur_c / 3;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (puzzle[cur_r][cur_c] == puzzle[box_r * 3 + r][box_c * 3 + c] && cur_r != box_r*3+r && cur_c != box_c*3+c) {
return false;
}
}
}
//중간에 걸리지 않은 경우 참
return true;
}
void solve(int size, int cur_size) {
if (size == cur_size) { //판을 다 채운 경우
stop = true; //끝남 표시
// 정답 출력
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
cout << puzzle[r][c] << " ";
}
cout << '\n';
}
return;
}
// 현재 위치 r, c 저장
int cur_r = blank[cur_size].first;
int cur_c = blank[cur_size].second;
for (int i = 1; i <= 9; i++) {
puzzle[cur_r][cur_c] = i; //1부터 9까지 대입
if (is_available(cur_r, cur_c)) { //참이면 다음 빈칸 채우기
solve(size, cur_size + 1);
}
//빈칸 채우기가 끝나거나 이전 숫자 때문에 다른 빈칸에 어떤 수도 들어갈 수 없는경우
if (stop == true) { //빈칸 채우기가 끝난 경우
return;
}
puzzle[cur_r][cur_c] = 0; //빈칸을 0으로 만들고 이전에 들어갈 수 있는 다른 숫자를 찾는다.
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//입력
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
cin >> puzzle[r][c];
if (puzzle[r][c] == 0) {
blank.push_back(make_pair(r, c));
}
}
}
solve(blank.size(), 0);
return 0;
}
Author And Source
이 문제에 관하여(백준 2580번 스도쿠), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsleeg98/백준-2580번-스도쿠저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)