스도쿠 문제 (백준2580번)
개요
백준 단계별로 풀어보기 ➡️ 백트래킹 ➡️ 스도쿠 문제입니다.
사실 스도쿠게임에 관심이 없어 한번도 해 본적이 없었는데 문제를 풀다보니 어렵지만 재미있는 게임이라는 생각이 듭니다. 🤔
|
| 스도쿠 예시 (출처 : 위키백과) |
1. 아홉 3×3 칸에 숫자가 1부터 9까지 하나씩만 들어가야 한다.
2. 아홉 가로줄에 숫자가 1부터 9까지 하나씩만 들어가야 한다.
3. 아홉 세로줄에 숫자가 1부터 9까지 하나씩만 들어가야 한다.
예시의 정답은,
|
| 스도쿠 정답 (출처 : 위키백과) |
위에 소개된 위키백과 스도쿠문제는 빈칸이 많아 난이도가 너무 높다는 생각이듭니다. 😥
아래 경우를 한번 살펴볼까요.
 |
| 백준 스도쿠 예제 |
훨씬 직관적이고 이해하기 좋습니다. 😀
예를 들면 맨 왼쪽 상단 빈칸은 가로줄, 세로줄, 3x3 모두 숫자1이 없으므로 빈칸을 1로 채우고 진행이 가능해 보입니다.
이렇게 진행해 가다 문제가 생기면 다시 돌아와 다른 숫자를 넣어보면 문제를 해결할 수 있을 것 같은 느낌이 듭니다.
 |
| 백준 스도쿠 정답 |
재귀호출과 백트래킹(Back-tracking) 알고리즘을 활용해 풀어보았습니다.
문제에 대한 설명은 아래 링크를 참조 바랍니다.
소스코드
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 74 75 76 77 78 79 80 81 82 83 84 | #include <iostream>using namespace std;const int SIZE = 9;bool isOk(int arr[][SIZE], int r, int c, int n){ // 행, 열에 해당 숫자체크 for(int i=0; i<SIZE; i++) { if(arr[i][c]==n || arr[r][i]==n) return false; } // 3x3 숫자체크 int x = (c/3)*3; int y = (r/3)*3; for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { if(arr[i+y][j+x]==n) return false; } } return true;}bool sudoku(int arr[][SIZE]){ for(int i=0; i<SIZE; i++) { for(int j=0; j<SIZE; j++) { // 빈칸(0)이면, 1~9 넣어보기 if(arr[i][j]==0) { for(int k=1; k<=9; k++) { if(isOk(arr, i, j, k)) { arr[i][j] = k; if(sudoku(arr)==true) return true; // 실패시 되돌리기(백트래킹) arr[i][j] = 0; } } // 1~9 모두 실패 return false; } } } return true;}int main(){ // 입력처리 int arr[SIZE][SIZE]; for(int i=0; i<SIZE; i++) { for(int j=0; j<SIZE; j++) { cin >> arr[i][j]; } } if(sudoku(arr) == true) { //출력하기 for(int i=0; i<SIZE; i++) { for(int j=0; j<SIZE; j++) { cout << arr[i][j] << ' '; } cout << '\n'; } } return 0;} |
앞서 소개한 백준문제를 대입한 결과는 다음과 같습니다.
|
| 코드 실행결과 |
코드 설명
스도쿠를 풀기 위해 백트래킹(Back-tracking) 알고리즘 사용.
백트래킹이란?
가능한 모든 경우를 시도하면서 정답을 찾되,
"이 길은 틀렸어!"라고 판단되면 이전으로 돌아가 다른 길을 시도하는 방법.
즉, 재귀 함수를 이용해서 숫자를 하나씩 넣어보고, 안 되면 되돌리는 방식으로 문제를 해결.
전체적인 코드의 구조는 3개의 함수로 구성.
1. isOk(int arr[][SIZE], int r, int c, int n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | bool isOk(int arr[][SIZE], int r, int c, int n){ // 행, 열에 해당 숫자체크 for(int i=0; i<SIZE; i++) { if(arr[i][c]==n || arr[r][i]==n) return false; } // 3x3 숫자체크 int x = (c/3)*3; int y = (r/3)*3; for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { if(arr[i+y][j+x]==n) return false; } } return true;} |
n을 (r, c) 위치에 넣을 수 있는지 체크하는 함수.
- 행과 열에서 숫자가 중복되는지 확인.
- 3x3 격자에서 숫자가 중복되는지 확인.
만약 숫자가 중복되지
않는다면 true, 중복된다면 false를 반환.
2. sudoku()
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 | bool sudoku(int arr[][SIZE]){ for(int i=0; i<SIZE; i++) { for(int j=0; j<SIZE; j++) { // 빈칸(0)이면, 1~9 넣어보기 if(arr[i][j]==0) { for(int k=1; k<=9; k++) { if(isOk(arr, i, j, k)) { arr[i][j] = k; if(sudoku(arr)==true) return true; // 실패시 되돌리기(백트래킹) arr[i][j] = 0; } } // 1~9 모두 실패 return false; } } } return true;} |
- 빈 칸(0)이 있는 위치를 탐색.
- 빈 칸(0) 이면 1부터 9까지 숫자를 하나씩 넣기.
- 만약 isOk() 함수의 리턴값이,
true이면 (이 숫자가 해당 위치에 가능), 재귀 호출(sudoku(arr))을 통해 다음 칸으로.
false이면, 이전 숫자로 되돌리고 다시 시도.(백트래킹)
- 진행하며
모든 빈 칸이 채워지면 true를 반환, 정답 출력
3. main()
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 | int main(){ // 입력처리 int arr[SIZE][SIZE]; for(int i=0; i<SIZE; i++) { for(int j=0; j<SIZE; j++) { cin >> arr[i][j]; } } if(sudoku(arr) == true) { //출력하기 for(int i=0; i<SIZE; i++) { for(int j=0; j<SIZE; j++) { cout << arr[i][j] << ' '; } cout << '\n'; } } return 0;} |
- arr[9][9], 2차원 배열 입, 출력을 담당.
이상으로 모든 설명을 마칩니다. 감사합니다.
댓글
댓글 쓰기