백준 2580번 스도쿠 내가 푼 코드(C++, 검증해보면 유용한 반례)

DFS 대표유형

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int arr[9][9];

bool Check_row(int target, int row_num) {
	for (int col_num = 0; col_num < 9; col_num++) {
		if (arr[row_num][col_num] == target) return false;
	}
	return true;
}

bool Check_col(int target, int col_num) {
	for (int row_num = 0; row_num < 9; row_num++) {
		if (arr[row_num][col_num] == target) return false;
	}
	return true;
}

bool Check_square(int target, int row_num, int col_num) {
	int row = row_num / 3 * 3;
	int col = col_num / 3 * 3;
	for (int i = row; i < row + 3; i++) {
		for (int j = col; j < col + 3; j++) {
			if (arr[i][j] == target) return false;
		}
	}
	return true;
}

bool Check_target(int target, int row_num, int col_num) {
	if (Check_row(target, row_num) && Check_col(target, col_num) && Check_square(target, row_num, col_num)) return true;
	return false;
}

void Print_sdoku() {
	for (int u = 0; u < 9; u++) {
		for (int y = 0; y < 9; y++) {
			printf("%d ", arr[u][y]);
		}
		printf("\n");
	}
	exit(0);
}

void Dfs(int a, int b) {
	if (arr[a][b] != 0) {
		if (a == 8 && b == 8) Print_sdoku();
		if (b + 1 == 9) Dfs(a + 1, 0);
		else Dfs(a, b + 1);
	}
	else {
		for (int j = 1; j <= 9; j++) {
			if (Check_target(j, a, b)) {

				arr[a][b] = j;
				if (a == 8 && b == 8) Print_sdoku();
				if (b + 1 == 9) Dfs(a + 1, 0);
				else Dfs(a, b + 1);
				arr[a][b] = 0;
			}
		}
		return;
	}
}

int main() {
	int i, j;
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			scanf("%d", &arr[i][j]);
		}
	}

	Dfs(0, 0);
}

• 스도쿠의 유효 범위는 행(r)과 열(c) 모두 인덱스 0부터 8까지이며 arr 배열에 입력 사항을 담았다.
• 나의 코드는 스도쿠를 위에서부터 아래로, 좌에서 우로 비어있는 숫자를 채워나가도록 했다.
• 재귀 함수의 종료 조건은 r=8 이고 c=8 일때 1. arr[8][8]이 0이 아니거나 2. 0일 경우 유효성 검사를 해서 통과한 좌표를 배열에 저장하고 배열의 모든 원소를 출력한 후 프로그램을 즉시 종료하면 된다.
• 재귀 함수는 크게 arr[r][c]가 0일 때와 0이 아닐 때로 나눌 수 있다. 0일 때에만 for문으로 1부터 9까지 숫자를 차례대로 넣어서 유효성 검사를 통과하면 배열에 저장하며 재귀함수를 호출하고 이것이 종료되면 arr[r][c]를 다시 0으로 초기화하여야 한다. 0일 때와 0이 아닐 때 모두 스도쿠 상에서 다음 좌표를 인자로 주어 재귀 함수를 재호출한다.
• 여기서 유효성 검사란 현재 좌표의 행에 있는 모든 열의 원소(Check_row), 현재 좌표의 열에 있는 모든 행의 원소(Check_col), 현재 좌표가 속한 3*3 정사각형에 들어 있는 모든 원소(Check_square)를 모두 검증하는 것을 말한다.

Test Case 1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

Test Case 1(출력 예시)
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

Test Case 2
0 2 0 9 0 5 0 0 0
5 9 0 0 3 0 2 0 0
7 0 0 6 0 2 0 0 5
0 0 9 3 5 0 4 6 0
0 5 4 0 0 0 7 8 0
0 8 3 0 2 7 5 0 0
8 0 0 2 0 9 0 0 4
0 0 5 0 4 0 0 2 6
0 0 0 5 0 3 0 7 0

Test Case 2(출력 예시)
3 2 1 9 7 5 6 4 8
5 9 6 8 3 4 2 1 7
7 4 8 6 1 2 9 3 5
1 7 9 3 5 8 4 6 2
2 5 4 1 9 6 7 8 3
6 8 3 4 2 7 5 9 1
8 1 7 2 6 9 3 5 4
9 3 5 7 4 1 8 2 6
4 6 2 5 8 3 1 7 9

Test Case 3
0 3 0 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
0 6 0 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

Test Case 3(출력 예시)
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1