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

1. 문제 이해

문제 자체 그대로 스도쿠를 푸는 문제이다!
9x9 의 Board가 주어지면, 빈 값은 0 으로 채워져서 입력으로 주어진다.
이러한 상황에서, 각 0 에 스도쿠 규칙데로 0에 알맞은 값을 채워주는 것이 문제이다.

2. 소스 코드

#include<vector>
#include<iostream>
#include<string>
#include<queue>
#include<stdlib.h>
using namespace std;
vector<vector<int>>arr;
struct Point {
	int r;
	int c;
};
vector<Point> po;
bool check(int x,int y , int val) {
	//가로 
	vector<int>sample;
	vector<int>sample2;
	for (int i = 0; i < 9; i++) {
		if (arr[i][y] == val)return false;
		if (arr[x][i] == val)return false;
	}
	//3x3
	int a, b;
	a = x / 3;
	b = y / 3;
	a = 3 * a;
	b = 3 * b;
	for (int i = a; i < a + 3; i++) {
		for (int j = b; j < b + 3; j++) {
			if (arr[i][j] == val)return false;
		}
	}
	return true;   
}
void sdoku(int cnt) {
	if (cnt == po.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)cout << arr[i][j] << " ";
			cout << "\n";
		}
		exit(0);
	}

	Point temp=po[cnt];
	int x = temp.r;
	int y = temp.c;
	for (int i = 1; i <= 9; i++) {
		if (check(x, y, i))
		{
			arr[x][y] = i;
			sdoku(cnt + 1);
			arr[x][y] = 0;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	for (int i = 0; i < 9; i++) {
		vector<int> sub;
		for (int j = 0; j < 9; j++) {
			int a;
			cin >> a;
			if (a == 0) {
				Point temp;
				temp.r = i;
				temp.c = j;
				po.push_back(temp);
			}
			sub.push_back(a);
		}
		arr.push_back(sub);
	}
	sdoku(0);
}

3. 풀이 방식

이 문제는 백준에 단계별 문제 중 백트래킹에 해당하는 문제였다.
그렇기에 아래 단계를 거쳐 풀이를 진행했다.

1. 값이 0인 애들의 좌표를(x,y) vector에 차곡차곡 저장했다.
2. 좌표를 하나하나 꺼내며 1~9 사이에 값을 무작위로 넣어줬다.
3. check 함수를 만들었고, 여기서는 가로/세로/3x3사각형 조건을 만족하는지 확인해 줬다.
4. check가 맞아 떨어지면, 그 다음 좌표가 들어간다,
5. 근데 만약에 스도쿠를 만족하지 못한다? 이러면 Cut 하고 결국 2에서 다른 값이 들어간다.

이러한 절차를 거치는 dfs 를 구현하였고, 풀었다.

4. 얻어가는 Tip

백트래킹은 사실상 DFS 와 마찬가지인 것 같다. (근데 단계별에선 백트래킹이 먼저 있는게 사실 살짝 의아한 것 같기도하다.)
깊이 탐색을 하며 답이나오면 이를 종료 시키고, 아닐 거 같으면 중간에 Cut 한다는게 핵심이론인 것 같다.

DFS , 백트래킹 기법을 쓰는 문제에선 주로 visit 배열이 쓰이는 것 같다.
(꼭 visit 이 아니더라도, 재귀로 들어가는 과정에서 특정값을 업데이트 함을 말한다.)
그리고 재귀로 따라 들어갈때는 항상 Count+1 하는 방식으로 찾아간다.

exit(0) 을 통해서 정답을 만나는 순간 프로그램을 종료시키는 것으로 빠르게 끝낸다. (스도쿠 답은 여러가지 일 수 있기 때문이다.)