[c++] 백준 2580 - 스도쿠(재귀호출, 백트래킹)

0. [c++] 백준  -

https://www.acmicpc.net/problem/2580

1. 풀이

재귀호출을 활용해 문제를 쉽게 해결하도록 해보았다.

1) 우선 조건을 확인하는 bool check 함수 제작

이 함수는 지금 대입해볼 숫자가 들어갈 수 있는지 확인해주는 역할을 수행한다.

2) 숫자를 집어넣는 과정을 자동화

스도쿠를 풀기 위해 아직 발견되지 않는 곳들에 1~9의 모든 수를 대입해 보는 과정을 진행 할 것이다.

그 과정을 재귀호출을 활용해 자동화를 해주었다..

2. 소스코드

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

#include<iostream> #include<vector>   using namespace std;   int board[9][9]; vector<pair<int, int>> point; bool print_once;   //기본 스도쿠 규칙을 만족하는지 확인한다. bool check(int y, int x, int num) {     //x,y축에 동일한 수가 존재하는지 확인     for (int i = 0;i < 9;i++) {         if (board[y][i] == num)             return false;         else if (board[i][x] == num)             return false;     }     //3*3칸에 동일한 수가 존재하는지 확인     for (int i = (y / 3) * 3;i < (y / 3) * 3 + 3;i++) {         for (int j = (x / 3) * 3;j < (x / 3) * 3 + 3;j++) {             if (board[i][j] == num)                 return false;         }     }     //동일한 수가 없으면 true를 반환     return true; }   //스도쿠에 아직 발견되지 않은 수의 개수만큼 재귀법을 활용해 해결하도록 하였다. void solve_sudoku(int N) {     //만일 N에 도달할 하였다면, 모든 조건을 만족시키는 해답이다.     //즉, 출력을 하고 함수를 종료한다.     if (N == point.size()) {         if (!print_once) {             for (int i = 0;i < 9;i++) {                 for (int j = 0; j< 9;j++)                     cout << board[i][j] << " ";                 cout << endl;             }             print_once = true;         }     }     else {         //이번 수의 y,x좌표를 vector에서 가져온다.         int y = point[N].first;         int x = point[N].second;         //1~9까지 모든 수를 넣어본다.         for (int num = 1;num <= 9;num++) {             //조건을 만족하는지 확인             if (check(y, x, num)) {                 //조건을 만족하면 수를 넣고                 board[y][x] = num;                 //재귀함수를 호출한다.                 solve_sudoku(N + 1);                 //이후 함수가 종료된 이후에는 0으로 초기화를 해준다.                 board[y][x] = 0;             }         }     } }   int main() {     for (int i = 0;i < 9;i++) {         for (int j = 0; j< 9;j++) {             cin >> board[i][j];             if (board[i][j] == 0)                 point.push_back({ i,j });         }     }       solve_sudoku(0); } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!