[백준] 2580-스도쿠(C++)

문제링크:https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

일반적인 방법으로 풀면은 시간초과입니다.

 

dfs를 사용하고 이미 확인한 값에 대해서는 탐색하지 않는 백트래킹 기법을 사용해야 하는 어려운 문제였습니다.

 

 

이문제에서의 핵심은

bool row[9][10] = { 0 };
bool col[9][10] = { 0 };
bool square[9][10] = { 0 };

 세가지 방문여부입니다. row는 해당 행에서 수를 탐색했는지 여부, col은 열에서 수를 탐색했는지 여부, square는 속하는 3x3에서 수를 탐색했는지 여부를 판단합니다.

 

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];



			if (arr[i][j] != 0)
			{
				row[i][arr[i][j]] = true;
				col[j][arr[i][j]] = true;
				square[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
			}


		}

	dfs(0);



}

위 처럼 수를 입력받으면 row, col, square에 방문 수를 저장합니다. 

row[i][j] 라면 i행에서 j값을 방문했는지 여부를 표시합니다 즉 row[1][9]= true 면은 1행에 9는 존재한다는 의미입니다.

col과 square 모두 같은 맥락입니다.

이때 스퀘어는 

위와 같은 구조로 진행됩니다. (출처: 얍문님 티스토리)  

 

그렇기 때문에 (y/3)*3 + x/3 을 통해서 해당 위치에 표시하는 것입니다.

 

 

 

정답코드입니다. cnt값을 올려주며 진행하게 됩니다. 81일때에는 모든 값들이 채워져 있는 것이기에 종료하게 됩니다.

이때 exit(0)를 이용해서 바로 프로세스를 종료해버리면 시간을 단축시킵니다. 천천히 이해해보세요.

#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;

int arr[9][9] = { 0 };
bool row[9][10] = { 0 };
bool col[9][10] = { 0 };
bool square[9][10] = { 0 };




void dfs(int cnt) {

	if (cnt == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << arr[i][j] << ' ';
			cout << endl;
		}
		exit(0);
	}
	int y = cnt / 9;
	int x = cnt % 9;

	if (arr[y][x] != 0)
		dfs(cnt + 1);
	else {
		
		for (int i = 1; i <= 9; i++) {
			if (row[y][i] == 0 && col[x][i] == 0 && square[(y / 3) * 3 + (x / 3)][i] == 0) {
				row[y][i] = 1;
				col[x][i] = 1;
				square[(y / 3) * 3 + (x / 3)][i] = 1;

				arr[y][x] = i;
				dfs(cnt + 1);
				arr[y][x] = 0;

				row[y][i] = 0;
				col[x][i] = 0;
				square[(y / 3) * 3 + (x / 3)][i] = 0;

			}

		}

	}


	return;
	
}


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];



			if (arr[i][j] != 0)
			{
				row[i][arr[i][j]] = true;
				col[j][arr[i][j]] = true;
				square[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
			}


		}

	dfs(0);



}