<Baekjoon> #2580 DFS_Sudoku c++

#2580 스도쿠

빈 칸을 채울 때 3x3 정사각형 내에서 숫자를 겹치지 않게 하는 부분과 시간 초과때문에 힘든 문제같다

1. vector<pair<int, int>>vp;
   먼저 스도쿠 판에 숫자를 입력 받을 때 빈 공간 즉, 0으로 입력 받는 부분의 좌표를 vp에 저장하고 받을 때마다 cnt++를 해주어 전체 빈 공간의 좌표와 개수를 저장한다

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) {
				vp.push_back(make_pair(i, j));
				cnt++;
			}
		}
	}

2. void dfs (int idx)

• idx는 현재 몇 번 째 빈 공간의 좌표 쌍 (vp[idx].first, vp[idx].second)를 채우는 것인지 체크하기 위함으고 dfs 함수의 종료 조건은 idx==cnt 일 때 즉, 모든 빈 공간의 좌표를 채웠을 때이다

	if (idx == cnt) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++)
				printf("%d ", board[i][j]);
			printf("\n");
		}
		return;
	}

• 빈 공간에 숫자를 채워 넣기
  빈 공간에는 1~9까지의 숫자가 들어갈 수 있으며 이 숫자가 들어갈 수 있는 숫자인지 check함수에서 유효성을 검사한 후 들어갈 수 있으면 dfs(idx+1)를 호출하여 다음 빈 공간에 대해 1~9까지 채워보며 유효성을 검사한다
  만약 1~9까지 다 채웠는데 숫자를 채울 수 없으면 다시 0을 넣고 그 전의 빈칸부터 다시 채운다

	for (int i = 1; i <= N; i++) {
		board[vp[idx].first][vp[idx].second] = i;
		if (check(vp[idx])) dfs(idx + 1);
		if (found) return;
	}
	board[vp[idx].first][vp[idx].second] = 0;

3.bool check(pair<int, int> p)

• 같은 행과 열에 지금 막 빈칸에 채워 넣은 숫자와 같은 숫자가 있는지 확인

	for (int i = 0; i < N; i++) {
		if (board[p.first][i] == board[p.first][p.second] &&
			i != p.second) return false;
		if (board[i][p.second] == board[p.first][p.second] &&
			i != p.first) return false;
	}

• 3x3 정사각형 안에 지금 막 빈칸에 채워 넣은 숫자와 같은 숫자가 있는지 확인

	int sq_y = p.first/3; 
    int sq_x = p.second/3;
    //지금 좌표가 가로,세로로 몇 번 째 정사각형에 속하는지 알기 위해
    //{0,1,2}= 0, {3,4,5}=1, {6,7,8}=2

	for (int i = 3*sq_y; i <3*sq_y + 3; i++) {
		for (int j = 3*sq_x; j < 3*sq_x + 3; j++) {
			if (board[i][j] == board[p.first][p.second]) {
				if (i != p.first && j != p.second)
					return false;
			}
		}
	}

• 이 모든 조건에 걸리지 않으면 true를 return

전체 코드

#include <iostream>
#include <vector>
using namespace std;
const int N = 9;
int board[N][N];
int cnt = 0;
bool found = false;
vector<pair<int, int>>vp;

bool check(pair<int, int> p) {

	int sq_y = p.first/3;
	int sq_x = p.second/3;

	for (int i = 0; i < N; i++) {
		if (board[p.first][i] == board[p.first][p.second] &&
			i != p.second) return false;
		if (board[i][p.second] == board[p.first][p.second] &&
			i != p.first) return false;
	}
	for (int i = 3*sq_y; i <3*sq_y + 3; i++) {
		for (int j = 3*sq_x; j < 3*sq_x + 3; j++) {
			if (board[i][j] == board[p.first][p.second]) {
				if (i != p.first && j != p.second)
					return false;
			}
		}
	}
	return true;
}
void dfs(int idx) {
	if (idx == cnt) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++)
				printf("%d ", board[i][j]);
			printf("\n");
		}
		return;
	}
	for (int i = 1; i <= N; i++) {
		board[vp[idx].first][vp[idx].second] = i;
		if (check(vp[idx])) dfs(idx + 1);
		if (found) return;
	}
	board[vp[idx].first][vp[idx].second] = 0;
}

int main() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) {
				vp.push_back(make_pair(i, j));
				cnt++;
			}
		}
	}
	dfs(0);
	return 0;
}