백준 - 2239 스도쿠

 

해결과정

처음 생각은 인간의 기초 상식으로 접근하여 각 칸마다 순회를 하며 반드시 특정 숫자여야 되는곳 ex) 가로 세로 square부분을 고려했을때 특정 숫자 만 되는 경우 값을 채우는 형식으로 하였지만 문제 조건에 맞지 않고 그런공간이 없을시 실패하는 당연한 실패였다

 

두번째 도전은 탐색을 떠나자 라는 식으로 재귀함수를 이용해 탐색을 하였는데 성공했다..

솔직히 시간초과를 각오하고 그냥 해본건데 성공해서 찜찜한 문제여서 질문을 남겼다 답변이 돌아온다면 다시 후기에 그 이유를 적어보겠다

 

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<deque>
#include<unordered_set>
#include<unordered_map>
#include<cmath>

#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

typedef long long ll;

int board[10][10];
int col[10][10];
int row[10][10];
int square[10][10];




void renewal(int number, int y, int x) {
	row[y][number]++;
	col[x][number]++;
	square[(y - 1) / 3 * 3 + (x - 1) / 3 + 1][number]++;
}

void erase(int number, int y, int x) {
	row[y][number]--;
	col[x][number]--;
	square[(y - 1) / 3 * 3 + (x - 1) / 3 + 1][number]--;
}

bool travel(int num) {
	if (num == 81) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				if (board[i][j] == 0) {
					return false;
				}
			}
		}
		
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				cout << board[i][j];
			}
			cout << '\n';
		}
		return true;
	}

	int y = num / 9 + 1;
	int x = num % 9 + 1;

	if (board[y][x] != 0) {
		if (travel(num + 1)) {
			return true;
		}
		else {
			return false;
		}
	}
	
	for (int i = 1; i <= 9; i++) {
		if (row[y][i] == 0 && col[x][i] == 0 && square[(y - 1) / 3 * 3 + (x - 1) / 3 + 1][i] == 0) {
			board[y][x] = i;
			renewal(i, y, x);
			if (travel(num + 1)) {
				return true;
			}
			board[y][x] = 0;
			erase(i, y, x);
		}
	}

	return false;
}

int main() {
	Fast;
	
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			char c;
			cin >> c;
			board[i][j] = c - '0';
			row[i][board[i][j]]++;
			col[j][board[i][j]]++;
			square[(i - 1) / 3 * 3 + (j - 1) / 3 + 1][board[i][j]]++;
		}
	}

	travel(0);

	return 0;
	
}

 

후기