스도쿠 문제다.
정답률 29퍼센트인걸 보고 몸을 떨었다.
근데 이게 중등 초등 올림피아드 문제라니..
문제를 풀면서 느낀점이 두가지 있다.
- 문제가 풀리지 않거나 헷갈릴 때, 브레이크 걸고 일일이 디버깅해보는 것이 시간이 오래 걸리긴 하지만 문제풀이엔 정말 도움이 된다.
- 그리고 항상 느끼는 거지만, 풀고 다른 사람들의 풀이를 봐야 내 실력이 느는 것 같다.
일단 아래는 내가 짠 코드다. 좀 길다.
#include <stdio.h>
#include <stdlib.h>
// 현재 써도 되는 것들을 모아서 만들어 놨다가, 거기서 하나씩 뽑아가며 재귀
// 넣을 수 있는 값을 찾는 포문 안에서, 값을 찾을 때마다 재귀호출.
// 하나의 재귀에서 하나의 셀을 맡음.
int sdo(int **a, int x, int y) {
int temp[10] = {0, }; // 넣을 수 있는 값들 저장할 배열.
for(int i = x; i < 9; i++) {
for(int j = y; j < 9; j++) {
// 없는 값 확인.
if(a[i][j] == 0) {
int m;
// 해당 위치와 같은 행의 값들 모두 수집.
for(m = 0; m < 9; m++) {
temp[a[i][m]]++;
}
// 해당 위치와 같은 열의 값들 모두 수집.
for(m = 0; m < 9; m++) {
temp[a[m][j]]++;
}
// 9칸 영역 중 해당 위치가 속해 있는 곳의 모든 값들을 수집.
for(m = (i/3)*3; m < (i/3)*3+3; m++) {
for(int n = (j/3)*3; n < (j/3)*3+3; n++) {
temp[a[m][n]]++;
}
}
// 쓸 수 있는 값들을 찾으며 재귀호출
for(m = 1; m < 10; m++) {
if(temp[m]==0) { // 쓸 수 있는 값을 찾았다.
a[i][j] = m;
/*
sdo 재귀 호출문으로 넘길 '다음 위치값 설정' 과정인데, 그냥 i, j로 넘겨주면 알아서 이중포문에서 작동해주긴 함.
int xx = i, yy = j;
if(++yy > 8) {
xx++; yy = 0;
if(xx>8) return 0;
}*/
if(!sdo(a, i, j)) // 0은 8 x 8을 지나 종료되었을 때를 뜻하며, 이는 정상적으로 뽑기를 마쳤음을 나타낸다.
return 0;
else // 만약 1을 반환했다면, 앞의 재귀가 뽑을 경우의 수를 찾을 수 없다는 경우이므로 현재의 값을 재설정해준다.
a[i][j] = 0;
}
}
if(m==10) { // 쓸 수 있는 값을 찾지 못했다는것은, 다시 뽑아야 한다는 것이므로 1을 반환하여 이전 재귀에서 재시도를 요청한다.
return 1;
}
}
}
y = 0; // i와 j값을 함수입력값으로 초기화받아 시작위치를 지정받지만, 0을 찾는 과정에서 j가 끝에 다다른 뒤엔 다시 0열부터 시작해줘야하므로 코딩해준다.
}
return 0;
}
int main() {
int **pos; // 스도쿠 판
pos = (int **)calloc(9, sizeof(int *));
for(int i = 0; i < 9; i++) {
pos[i] = (int *)calloc(9, sizeof(int));
}
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
scanf("%d", &pos[i][j]);
}
}
sdo(pos, 0, 0);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
printf("%d ", pos[i][j]);
}
putchar('\n');
}
free(pos);
}
(주석이 거의 코드길이)
다른 분들의 코드를 보면서 배운점이 있다.
근데 이분 코드의 전체적 흐름이 좋은데, 잘 실행되는건지는 모르겠다 ㅋㅋ...
이분 IndexOutOfBounds 에러 뜨실 것 같은데.. 안뜨시나...? 배열이 0~8, 0~8인데 i의 값이 1~9까지 인데 이걸 못담아낼 것 같다.
#include <stdio.h>
int A[9][9];
int R[9][9];
int C[9][9];
int S[9][9];
int done;
void sudoku(int n) {
int x = n / 9;
int y = n % 9;
if(n == 9*9) {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
printf("%d ", A[i][j]);
}
if(i < 8) printf("\n");
}
exit(0);
}
if(A[x][y] == 0) {
for(int i = 1; i <= 9; i++) {
if(R[x][i] || C[y][i] || S[(x/3)*3+(y/3)][i]) continue;
R[x][i] = 1;
C[y][i] = 1;
S[(x/3)*3+(y/3)][i] = 1;
A[x][y] = i;
sudoku(n+1);
R[x][i] = 0;
C[y][i] = 0;
S[(x/3)*3+(y/3)][i] = 0;
A[x][y] = 0;
}
} else {
sudoku(n+1);
}
}
int main(void) {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
scanf("%d", &A[i][j]);
if(A[i][j] != 0) {
R[i][A[i][j]] = 1;
C[j][A[i][j]] = 1;
S[(i/3)*3+(j/3)][A[i][j]] = 1;
}
}
}
sudoku(0);
}내가 그럼에도 불구하고 이 코드를 가져온 이유는, 배울 점이 두가지 있다.
1. 이분은 n을 전체 개수라고 두고, 행 / 열을 아래와 같이 구해냈다...
int x = n / 9;
int y = n % 9;다시봐도 대단하구만 그래..
2. 코드의 흐름이 좋다.
Row[행][1~9], Colum[열][1~9], S[사각형영역][1~9] 세 배열을 이용하는데, 각 행이나 열 또는 사격형 영역에 1~9까지의 인덱스에 값이 존재하면 1로 채워준다. 그리고 전체적인 흐름이, 백트랙의 흐름 다운 흐름을 보여주고 있다.
백트랙의 흐름이라면.. 말하자면 이런느낌?
재귀함수() {
for문 {
체크[]=1;
재귀함수();
체크[]=0;
}
}
내 코드도 흐름이 아예 이렇지 않지는 않다. 그래도 뭔가 코드가 깔끔하시달까..
+ 위의 indexoutofbounds 에 대한 내용
www.inflearn.com/questions/26768
결론 : 전역변수로 선언하면 여유롭게 잡힌다. 그리고 C에선 out of index를 컴파일러가 잡지 못한다. 이는 개발자가 알아서 주의해줘야한다. 이렇게 했다가 나중에 위험을 초래할 수 있으므로 주의.
+ 다른 분들의 소스
시간 날 때 스도쿠 관련해서 다른 분들의 코드를 더 많이 봐봐야겠다.
2021.03.13 복습
다시풀어봤다.
글을 다시보니, 백트래킹에 대한 개념에 틀린 부분이 있다.
가지치기에 대한 개념(노드의 유망성을 검사하여 필요치않은 노드는 검색하지 않아서 전체 경우를 도는 dfs랑은 다르다는 것)이 없다.
다시 푸는데도, 매우 힘들었다.
#include <stdio.h>
#include <stdlib.h>
int R[9][10]; // 0 ~ 8 각 행에 1 ~ 9 값이 존재하는지에 대한 체크배열
int C[9][10]; // 0 ~ 8 각 열에 1 ~ 9 값이 존재하는지에 대한 체크배열
/*
9 x 9 에서 3 x 3을 하나의 사각형으로 볼 때.
0 1 2
3 4 5
6 7 8
*/
int S[9][10]; // 0 ~ 8 각 사각형에 1 ~ 9 값이 존재하는지에 대한 체크배열
int arr[9][9]; // 스도쿠 판
int CLEAR = 0; // 끝나고도 재귀가 계속될수있어서, exit(0)으로도 종료할 수 있으나 CLEAR로 명시적선언.
void sdocu(int iter) {
if(CLEAR)
return;
int x = iter / 9;
int y = iter % 9;
if(iter == 81) {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
printf("%d ", arr[i][j]);
}
putchar('\n');
}
CLEAR = 1;
return;
}
if(!arr[x][y]) { // 0부분인 경우
for(int i = 1; i <= 9; i++) { // 1~9까지 숫자중 쓰일 수 있는 걸 체크함.
if(R[x][i] || C[y][i] || S[(x/3)*3 + (y/3)][i]) continue; // 쓰일 수 없으면 다시
R[x][i] = 1;
C[y][i] = 1;
S[(x/3)*3 + (y/3)][i] = 1;
arr[x][y] = i;
sdocu(iter + 1);
R[x][i] = 0;
C[y][i] = 0;
S[(x/3)*3 + (y/3)][i] = 0;
arr[x][y] = 0;
}
} else { // 1인 경우 다음으로.
sdocu(iter + 1);
}
}
int main() {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
scanf("%d", &arr[i][j]);
R[i][arr[i][j]] = 1; // i 행에, 해당 숫자가 있다는 것을 체크
C[j][arr[i][j]] = 1; // j 열에, 해당 숫자가 있다는 것을 체크
S[(i/3)*3 + (j/3)][arr[i][j]] = 1;
/*
9 x 9 에서 3 x 3을 하나의 사각형으로 볼 때.
0 1 2
3 4 5
6 7 8
*/
}
}
sdocu(0);
}
'[백준]' 카테고리의 다른 글
| [BaekJoon/백준] 14889번 & 다시보기 ★★★★★ (0) | 2020.12.11 |
|---|---|
| [BaekJoon/백준] 14888번 (0) | 2020.12.09 |
| [BaekJoon/백준] 9663번 (0) | 2020.12.07 |
| [BaekJoon/백준] 15652번 (0) | 2020.12.06 |
| [BaekJoon/백준] 15651번 (0) | 2020.12.05 |
