BOJ 2580 2239 스도쿠

백준 2580 : https://www.acmicpc.net/problem/2580

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

두 문제는 입력과 출력만 다를 뿐 같은 문제라고 봐도 된다.

지하철을 타면서 긴 시간을 통학하는게 지겨워 핸드폰에 스도쿠앱을 깔아서 하고있다. 정말 어려운것 같다. 답답하던 마음에 백준에 마침 스도쿠 문제가 있다는게 떠올라서 풀어보았다.

해결과정:

전체적인 풀이는 재귀를 이용한 완전탐색으로 풀었다는게 핵심이다. 

사람이 푸는것과 마찬가지로 풀었다. 가로, 세로, 사각형에 같은 수가 있는지를 판단하는것이다.

O(1)을 위해 메모이제이션을 이용하였다. 

row 를 예시로 들어서 row[n][number]는 n번째 세로줄에 number가 있는지 여부이다. 양수이면 존재

square은 9x9판을

1 2 3

4 5 6

7 8 9

로 나눠서 square[n][number] n번째 사각형에 number가 있는지 여부이다.

그리고 find함수로 완전탐색을 하였다. flag 변수를 두어 판이 다 채워졌는지를 확인해 불필요한 탐색을 막는다.

코드: (2580기준)

#include<iostream>
using namespace std;
int map[12][12], row[10][10], col[10][10], square[10][10], flag;

void find(int y, int x) {
	if (y == 9 && x == 10) flag = 1;
	else if (x == 10) find(y + 1, 1);
	else if (!map[y][x]) { //빈칸임?
		for (int i = 1; i <= 9; i++) {
			if (!row[y][i] && !col[x][i] && !square[((x + 2) / 3) + (((y - 1) / 3) * 3)][i]) {
				map[y][x] = i; // i 대입
				row[y][i] = col[x][i] = square[((x + 2) / 3) + (((y - 1) / 3) * 3)][i] = 1;
				find(y, x + 1);
				if (flag) break; //만약 스도쿠 다채워지면 도망치기
				map[y][x] = 0;
				row[y][i] = col[x][i] = square[((x + 2) / 3) + (((y - 1) / 3) * 3)][i] = 0;
			}
		}
	}
	else find(y, x + 1);
}

int main() {
	//freopen("input.txt", "r", stdin);
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			cin >> map[i][j];
			row[i][map[i][j]] = 1;
			col[j][map[i][j]] = 1;
			square[((j + 2) / 3) + (((i - 1) / 3) * 3)][map[i][j]] = 1;
		}
	}
	find(1, 1);
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			cout << map[i][j] <<' ';
		}
		cout << endl;
	}
}