[C/C++] 백준 - 2239번 : 스도쿠

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

2239번: 스도쿠

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

 

 

스도쿠 크기가 9X9의 크기로 작은 편이므로 모든 경우의 수를 확인하면서 진행하면 된다. 

따라서, 재귀를 이용한 백트래킹 기법으로 완전탐색을 구현한다.

 

나는 처음에 행과 열, 현재 위치를 고려한 3x3 삼각형 안에 해당 숫자가 존재하는지 확인하는 코드를 작성하였는데,

이 방법보다 bool배열을 이용하여 체크를 하는 방법으로 효율적인 코드를 작성할 수도 있다.

 

 

 

 

< 첫 번째 방법 - 하나 하나 반복문을 통해 확인 >

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int board[10][10];

void input() {
	for (int i = 1; i <= 9; i++) {
		string s; cin >> s;
		for (int j = 0; j < s.size(); j++) {
			board[i][j + 1] = s[j] - '0';
		}
	}
}

bool findRow(int y, int x, int v) {
	for (int i = 1; i <= 9; i++) {
		if (x != i  && board[y][i] == v) {
			return false;
		}
	}
	return true;
}

bool findCol(int y, int x, int v) {
	for (int i = 1; i <= 9; i++) {
		if (y!=i && board[i][x] == v) {
			return false;
		}
	}
	return true;
}

bool findSquare(int y, int x, int v) {
	int start_y, start_x, end_y, end_x;
	if (y % 3 != 0) {
		start_y = y / 3 * 3 + 1;
		end_y = y / 3 * 3 + 3;
	}
	else {
		start_y = (y / 3 - 1) * 3 + 1;
		end_y = y;
	}

	if (x % 3 != 0) {
		start_x = x / 3 * 3 + 1;
		end_x = x / 3 * 3 + 3;
	}
	else {
		start_x = (x / 3 - 1) * 3 + 1;
		end_x = x;
	}
	for (int i = start_y; i <= end_y; i++) {
		for (int j = start_x; j <= end_x; j++) {
			if ((y != i && x != j) && board[i][j] == v) {
				return false;
			}
		}
	}
	return true;
}

void go(int y, int x) {
	if (y == 10) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				cout << board[i][j];
			}
			ENDL;
		}
		exit(0);
	}
	
	
	if (board[y][x] != 0) {
		x == 9 ? go(y + 1, 1) : go(y, x + 1);
	}
	else {
		for (int i = 1; i <= 9; i++) {
			if (!findRow(y, x, i) || !findCol(y, x, i) || !findSquare(y, x, i)) continue;
			board[y][x] = i;

			x == 9 ? go(y + 1, 1) : go(y, x + 1);

			board[y][x] = 0;
		}
	}
}

int main() {
	fastio;
	input();	
	go(1, 1);

	return 0;
}

 

 

 

< 두 번째 방법 - bool 배열을 통해 바로 접근 >

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int board[10][10];
bool Row[10][10], Col[10][10], Sqare[15][10];

int returnArea(int y, int x) {
	if (1 <= y && y <= 3) {
		if (1 <= x && x <= 3) return 1;
		if (4 <= x && x <= 6) return 2;
		if (7 <= x && x <= 9) return 3;
	}
	else if (4 <= y && y <= 6) {
		if (1 <= x && x <= 3) return 4;
		if (4 <= x && x <= 6) return 5;
		if (7 <= x && x <= 9) return 6;
	}
	else {
		if (1 <= x && x <= 3) return 7;
		if (4 <= x && x <= 6) return 8;
		if (7 <= x && x <= 9) return 9;
	}
}

void reverse(int y, int x, int value) {
	Row[y][value] = !Row[y][value];
	Col[x][value] = !Col[x][value];
	Sqare[returnArea(y, x)][value] = !Sqare[returnArea(y, x)][value];
}

void input() {
	for (int i = 1; i <= 9; i++) {
		string s; cin >> s;
		for (int j = 0; j < s.length(); j++) {
			board[i][j + 1] = s[j] - '0';
			if (board[i][j + 1] != 0) {
				Row[i][board[i][j + 1]] = true;
				Col[j + 1][board[i][j + 1]] = true;
				Sqare[returnArea(i, j + 1)][board[i][j + 1]] = true;
			}
		}
	}
}

bool isValid(int y, int x, int value) {
	return (!Row[y][value] && !Col[x][value] && !Sqare[returnArea(y, x)][value]);
}


void go(int y, int x) {
	if (y == 10) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				cout << board[i][j];
			}
			ENDL;
		}
		exit(0);
	}


	if (board[y][x] != 0) {
		x == 9 ? go(y + 1, 1) : go(y, x + 1);
	}
	else {
		for (int i = 1; i <= 9; i++) {
			if (!isValid(y, x, i)) continue;
			board[y][x] = i;
			reverse(y, x, i);

			x == 9 ? go(y + 1, 1) : go(y, x + 1);

			board[y][x] = 0;
			reverse(y, x, i);
		}
	}
}


int main() {
	fastio;
	input();	
	go(1, 1);

	return 0;
}