(백준 2580번 스도쿠 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Backtracking 4

골드 4번 문제도 아직은 버겁다.. 좀 더 노력해보자!

 

백준 2580번

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

2580번: 스도쿠

#include <iostream>
#include <deque>
using namespace std;

int arr[9][9];
deque<pair<int, int>> dq;

bool checkRow(int x, int y, int num) {
	for (int j = 0; j < 9; j++) {
		if (y == j) continue;
		if (arr[x][j] == num) return false;
	}
	return true;
}

bool checkCol(int x, int y, int num) {
	for (int i = 0; i < 9; i++) {
		if (x == i) continue;
		if (arr[i][y] == num) return false;
	}
	return true;
}
bool check33(int x, int y, int num) {
	int row = int(x / 3) * 3;
	int col = int(y / 3) * 3;
	for (int i = row; i < row + 3; i++) {
		for (int j = col; j < col + 3; j++) {
			if (i == x && j == y) continue;
			if (arr[i][j] == num) return false;
		}
	}
	return true;
}
//잘못 짠 코드
/*bool BT(int curr_x, int curr_y) {
	cout << "current point : (" << curr_x << ", " << curr_y << ")" << endl;
	for (int i = 1; i < 10; i++) {
		arr[curr_x][curr_y] = i;
		cout << "current point : (" << curr_x << ", " << curr_y << ") and value : " <<i <<  endl;

		if (checkRow(curr_x, curr_y) && checkCol(curr_x, curr_y) && check33(curr_x, curr_y)) {
			if (dq.empty()) return true;
			int next_x = dq.front().first;
			int next_y = dq.front().second;
			dq.pop_front();
			if(BT(next_x, next_y)) return true;
			dq.push_front(make_pair(next_x, next_y));

		}
	}

	return false;
}
*/

bool BT(int curr_x, int curr_y, int num) {
	if (!checkRow(curr_x, curr_y, num)) return false;
	else if (!checkCol(curr_x, curr_y, num)) return false;
	else if (!check33(curr_x, curr_y, num)) return false;
	
	arr[curr_x][curr_y] = num;
	//★ 위치
	if (dq.empty()) return true;

	int next_x = dq.front().first;
	int next_y = dq.front().second;
	dq.pop_front();

	for (int i = 1; i < 10; i++) {
		if (BT(next_x, next_y, i)) return true;
	}
	dq.emplace_front(make_pair(next_x, next_y));

	arr[curr_x][curr_y] = 0;
	return false;
}

int main() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 0) {
				dq.emplace_back(make_pair(i, j));
			}
		}
	}
	int x = dq.front().first;
	int y = dq.front().second;
	dq.pop_front();

	for (int i = 1; i < 10; i++) {
		//★ 시작 숫자가 1일 필요는 없음
		if (BT(x, y, i)) break;
	}

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << endl;
	}
}

 

디버깅하다가 인내심을 다 써버렸다^^

 

이렇게 숫자를 대입해야 하는 문제는 위치와 함께 숫자를 input으로 추가하는 것 좋다!!!