백준[2580] - 스도쿠

문제

백준 2580 문제 보기

접근 방법

백트래킹을 활용해서 문제를 풀수 있다.

  • 입력받은 값들 중 빈 좌표를 따로 저장
  • 첫번째 저장된 좌표에 1~9까지 숫자를 대입하여 현재 스도쿠를 만족하는지 검사
  • 만족한다면 다음 좌표에서 1~9까지 숫자를 대입하고 검사를 반복

코드

#include <iostream>
#include <vector>
#include <utility>
#include <cstdlib>
using namespace std;
int sudoku[9][9];
vector<pair<int, int>> arr;
// 똑같은 숫자가 있는지 세로 검사
bool chk_vertical(int c, int num) {
for(int r = 0; r < 9; r ++) {
if(sudoku[r][c] == num) {
return false;
}
}
return true;
}
// 가로 검사
bool chk_horizontal(int r, int num) {
for(int c = 0; c < 9; c ++) {
if(sudoku[r][c] == num) {
return false;
}
}
return true;
}
// 3*3 네모난 모양 검사
bool chk_square(int r, int c, int num) {
r = r / 3;
c = c / 3;
for(int rr = r * 3; rr < (r * 3) + 3; rr ++) {
for(int cc = c * 3 ; cc < (c * 3) + 3; cc ++) {
if(sudoku[rr][cc] == num) {
return false;
}
}
}
return true;
}
void dfs(int idx) {
// 모든 좌표에 숫자를 넣었다면 정답 출력
if(idx == arr.size()) {
for(int i = 0; i < 9; i ++) {
for(int j = 0; j < 9; j ++) {
cout << sudoku[i][j] << " ";
}
cout << "\n";
}
exit(0);
}
// 1~9까지 숫자를 넣음
for(int num = 1; num <= 9; num ++) {
int r = arr[idx].first;
int c = arr[idx].second;
// 가로, 세로, 네모 모양을 검사해서 해당 숫자가 들어갈 수 있는지 확인
if(chk_vertical(c, num) && chk_horizontal(r, num) && chk_square(r, c, num)) {
// 들어갈 수 있다면 숫자를 넣음
sudoku[r][c] = num;
// 다음 좌표로 이동
dfs(idx + 1);
// 원상 복구
sudoku[r][c] = 0;
}
}
}
int main() {
for(int i = 0; i < 9; i ++) {
for(int j = 0; j < 9; j ++) {
cin >> sudoku[i][j];
// 비어있는 칸은 좌표를 따로 저장
if(sudoku[i][j] == 0) {
arr.push_back({ i, j });
}
}
}
// 1~9까지 숫자를 넣음
for(int num = 1; num <= 9; num ++) {
int r = arr[0].first;
int c = arr[0].second;
// 가로, 세로, 네모 모양으로 해당 num이 들어갈 수 있는지 확인
if(chk_vertical(c, num) && chk_horizontal(r, num) && chk_square(r, c, num)) {
sudoku[r][c] = num;
dfs(1);
sudoku[r][c] = 0;
}
}
return 0;
}
Share