BOJ 2239

스도쿠

문제출처

문제 해석

  • 제목 그대로 스도쿠를 푸는 문제입니다.
  • 답이 여러개가 나오는 경우 사전순으로 가장 앞서는 것을 출력합니다.

설계(5)

  • 백트래킹 문제로, 각 행과 열 그리고 3x3 박스의 상태를 저장한 후 해당 배열에 아직 포함되지 않은 숫자를 찾습니다.
  • 사전순으로 가장 앞서는 맵을 출력하기 위해서 처음에 입력을 받을 때, 0의 개수를 카운트 해놓고 탐색을 하면서 0이 있는 부분을 모두 채우면 출력을 한후 바로 리턴을 합니다.

구현(40)

코드
#include <iostream>
using namespace std;
#define MAXN 9

int bit_row[MAXN];
int bit_col[MAXN];
int bit_box[MAXN];
char map[MAXN][MAXN];
int total_cnt = 0;
bool flag = false;
bool check(int x, int y, int num) {
	if ((bit_row[x] & (1 << num)) ||
		(bit_col[y] & (1 << num)) ||
		(bit_box[int(x/3)*3+y/3] & (1<<num))) return false;
	return true;
}
void dfs(int x, int y, int cnt) {
	if (flag) return;
	if (cnt == total_cnt) {
		flag = true;
		for (int i = 0; i < MAXN; i++) {
			for (int j = 0; j < MAXN; j++) {
				cout << map[i][j];
			}
			cout << "\n";
		}
		return;
	}
	if (y == MAXN) dfs(x + 1, 0, cnt);
	if (map[x][y] != '0') dfs(x, y + 1, cnt);
	else {
		for (int i = 1; i <= 9; i++) {
			if (check(x, y, i)) {
				bit_row[x] |= (1 << i);
				bit_col[y] |= (1 << i);
				bit_box[int(x / 3) * 3 + y / 3] |= (1 << i);
				map[x][y] = i + '0';
				dfs(x, y + 1, cnt + 1);
				bit_row[x] &= ~(1 << i);
				bit_col[y] &= ~(1 << i);
				bit_box[int(x / 3) * 3 + y / 3] &= ~(1 << i);
				
			}
		}
		map[x][y] = '0';
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i < MAXN; i++) {
		cin >> map[i];
		for (int j = 0; j < MAXN; j++) {
			if (map[i][j] == '0') total_cnt++;
		}
	}
	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++) {

			if (map[i][j] != '0') {
				bit_row[i] |= (1 << (map[i][j] - '0'));
				bit_box[(i / 3) * 3 + j / 3] |= (1 << (map[i][j] - '0'));
			}
			if (map[j][i] != '0') {
				bit_col[i] |= (1 << (map[j][i] - '0'));
			}
			
		}
	}
	dfs(0, 0, 0);
	return 0;
}
디버깅
  • 처음에 현재 좌표에 숫자가 있는 경우와 없는 경우를 독립적인 경우로 구현을 하지 않아서, 숫자가 있는 경우에도 숫자를 채우는 부분으로 들어가도록 잘못구현이 되었습니다.
  • 그래서 현재 좌표가 있는 경우와 없는 경우로 나누어 탐색하도록 하였습니다.
제출결과
  • 156ms

마무리

  • 백트래킹 구현을 연습할 때 아주 많이 추천하는 문제로, 여태껏 풀어보지 않았습니다. 비트연산을 활용하여 더욱 간단하게 구현을 할 수 있었습니다.