백준 2239 - 스도쿠

문제링크

• 백준 2239

문제설명

• 9개의 3x3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우는 스도쿠 게임
• 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3x3 사각형에 1부터 9까지의 숫자가 중복 없이 나와야 한다.

문제접근

• 숫자를 채워야 하는 빈칸의 좌표들을 vector<pair<int, int>> node 에 담아둔다.
  • 백트래킹을 적용하기 위해서 가장 편리한 방법이다.
  • 노드로 관리하지 않고 좌표로 접근하면서 백트래킹을 구현했었는데 매번 빈칸을 찾아줘야 한다는 점은 시간을 많이 소요하게 되고, 로직적으로 문제가 발생해서 문제해결이 쉽지 않았다.
• vector<char> cand[x][y] 배열에는 현재 빈칸에 들어갈 수 있는 숫자 후보들을 담아둔다.
  • 1부터 9까지 차례대로 모든 숫자를 넣어볼 수는 있지만, 처음부터 걸러낼 수 있는 숫자들은 제거하는 것이 좋다고 판단했다/
• 정답이 여러 개인 경우 81자리의 숫자가 가장 작은 경우를 정답으로 출력한다는 의미는 작은 숫자들을 먼저 넣어서 스도쿠를 완성하도록 하라는 의미이다. 따라서, 가장 처음에 완성된 스도쿠를 정답으로 출력하고 exit(0) 을 호출하여 프로그램을 종료한다.
  • return 으로 재귀함수들을 모두 빠져나오도록 구현할 수 있지만, 시간초과에 걸렸다.

구현

#include <iostream>
#include <string>
#include <vector>
#include <memory.h>
#include <cctype>
#include <queue>
using namespace std;

vector<string> board, answer;
vector<char> cand[9][9];
vector<pair<int, int>> node;

void setCand(int x, int y) {
	int digit[10];
	memset(digit, 0, sizeof(digit));

	// check row
	for (int c = 0; c < 9; c++) {
		if (c == y) continue;
		digit[board[x][c] - '0'] = 1;
	}

	// check col
	for (int r = 0; r < 9; r++) {
		if (r == x) continue;
		digit[board[r][y] - '0'] = 1;
	}

	// check box
	int sx = (x / 3) * 3;
	int sy = (y / 3) * 3;
	for (int dx = 0; dx < 3; dx++) {
		for (int dy = 0; dy < 3; dy++) {
			if ((sx + dx == x) && (sy + dy == y)) continue;
			digit[board[sx + dx][sy + dy] - '0'] = 1;
		}
	}

	// set cand
	for (int i = 1; i <= 9; i++) {
		if (digit[i] == 0) cand[x][y].push_back(i+'0');
	}
}

void printAnswer() {
	for (auto ele : answer) {
		cout << ele << "\n";
	}
}

bool checkRow(int x, int y, char ele) {
	for (int c = 0; c < 9; c++) {
		if (c == y) continue;
		if (ele == board[x][c]) return true;
	}
	return false;
}

bool checkCol(int x, int y, char ele) {
	for (int r = 0; r < 9; r++) {
		if (r == x) continue;
		if (ele == board[r][y]) return true;
	}
	return false;
}

bool checkBox(int x, int y, char ele) {
	int sx = (x / 3) * 3;
	int sy = (y / 3) * 3;
	for (int dx = 0; dx < 3; dx++) {
		for (int dy = 0; dy < 3; dy++) {
			if ((sx + dx == x) && (sy + dy == y)) continue;
			if (board[sx + dx][sy + dy] == ele) return true;
		}
	}
	return false;
}

void playSdoku(int v) {
	if (v == node.size()) {
		answer = board;
		printAnswer();
		exit(0);
	}

	int xpos = node[v].first;
	int ypos = node[v].second;
	for (auto ele : cand[xpos][ypos]) {
		if (checkRow(xpos, ypos, ele) || checkCol(xpos, ypos, ele) || checkBox(xpos, ypos, ele)) continue;
		board[xpos][ypos] = ele;
		playSdoku(v + 1);
		board[xpos][ypos] = '0';
	}

}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	for (int i = 0; i < 9; i++) {
		string str;
		cin >> str;
		board.push_back(str);
	}

	// 빈칸과 후보 숫자 정하기
	for (int r = 0; r < 9; r++) {
		for (int c = 0; c < 9; c++) {
			if (board[r][c] == '0') {
				setCand(r, c);
			}
		}
	}
	// set node
	for (int r = 0; r < 9; r++) {
		for (int c = 0; c < 9; c++) {
			if (cand[r][c].size() == 0) continue;
			node.push_back(make_pair(r, c));
		}
	}
	playSdoku(0);
	printAnswer();

	return 0;
}