[백준] 2580번 : 스도쿠
문제 푼 날짜 : 2021-09-19
문제
문제 링크 : https://www.acmicpc.net/problem/2580
접근 및 풀이
문제의 제한사항에 아래와 같이 아주 친절하게 백트래킹 알고리즘을 이용하는 문제라고 명시되어있다.
백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다.
사실, 이 문제가 백트래킹으로 분류되어있어서 이미 알고는 있었지만, 모든 문제에 이런 제한사항이 있으면 얼마나 좋을까라는 생각을 잠시나마 해봤다..
아무튼 스도쿠는 아주 유명한 게임이 때문에 규칙은 너무나 유명하기도 해서 문제를 이해하는 데에 큰 어려움은 없었고, 아래의 생각대로 코드를 구현하였다.
- 주어진 입력에서 빈 칸의 갯수를 세어준다.(입력의 0)
- 이를 매개변수로 dfs를 구현해준다.
2-1. 매 빈 칸에 1부터 9까지 넣어보면서 빈 칸이 속한 행과 열, 3x3 정사각형까지 그 숫자가 들어갈 수 있는지 체크해준다.
2-2. 모든 빈 칸이 조건에 맞게 숫자가 채워지면 바로 return (스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다. 라고 했으므로 더 이상 찾을 필요가 없기 때문이다.)
코드
// 백준 2580번 : 스도쿠
#include <iostream>
#include <vector>
using namespace std;
int board[9][9];
vector<pair<int, int>> pos;
int zero_cnt = 0;
bool canFill(pair<int, int> point) {
for (int i = 0; i < 9; i++) {
if (board[point.first][i] == board[point.first][point.second] && i != point.second) {
return false;
}
if (board[i][point.second] == board[point.first][point.second] && i != point.first) {
return false;
}
}
int row_scope = point.first / 3;
int col_scope = point.second / 3;
for (int i = row_scope * 3; i < row_scope * 3 + 3; i++) {
for (int j = col_scope * 3; j < col_scope * 3 + 3; j++) {
if (board[i][j] == board[point.first][point.second] && i != point.first && j != point.second) {
return false;
}
}
}
return true;
}
bool make_sudoku(int N) {
if (N == zero_cnt) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << board[i][j] << ' ';
}
cout << '\n';
}
return true;
}
for (int num = 1; num <= 9; num++) {
board[pos[N].first][pos[N].second] = num;
if (canFill(pos[N])) {
if (make_sudoku(N + 1)) {
return true;
}
}
}
board[pos[N].first][pos[N].second] = 0;
return false;
}
int main() {
ios_base::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];
if (board[i][j] == 0) {
pos.push_back(make_pair(i, j));
zero_cnt++;
}
}
}
make_sudoku(0);
return 0;
}
결과
// 백준 2580번 : 스도쿠
#include <iostream>
#include <vector>
using namespace std;
int board[9][9];
vector<pair<int, int>> pos;
int zero_cnt = 0;
bool canFill(pair<int, int> point) {
for (int i = 0; i < 9; i++) {
if (board[point.first][i] == board[point.first][point.second] && i != point.second) {
return false;
}
if (board[i][point.second] == board[point.first][point.second] && i != point.first) {
return false;
}
}
int row_scope = point.first / 3;
int col_scope = point.second / 3;
for (int i = row_scope * 3; i < row_scope * 3 + 3; i++) {
for (int j = col_scope * 3; j < col_scope * 3 + 3; j++) {
if (board[i][j] == board[point.first][point.second] && i != point.first && j != point.second) {
return false;
}
}
}
return true;
}
bool make_sudoku(int N) {
if (N == zero_cnt) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << board[i][j] << ' ';
}
cout << '\n';
}
return true;
}
for (int num = 1; num <= 9; num++) {
board[pos[N].first][pos[N].second] = num;
if (canFill(pos[N])) {
if (make_sudoku(N + 1)) {
return true;
}
}
}
board[pos[N].first][pos[N].second] = 0;
return false;
}
int main() {
ios_base::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];
if (board[i][j] == 0) {
pos.push_back(make_pair(i, j));
zero_cnt++;
}
}
}
make_sudoku(0);
return 0;
}
피드백
역시 조금만 어려워지니 구현하는데 시간이 오래걸렸다.. 문제를 풀 때 좀 더 집중하자.
Author And Source
이 문제에 관하여([백준] 2580번 : 스도쿠), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bestcoders/백준-2580번-스도쿠저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)