[C++] BOJ(백준) 2580 스도쿠

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

2580번: 스도쿠

 

백트래킹 문제다.

 

9 x 9로 배열이 크지 않아 백트래킹을 이용했다.

배열에서 0인 칸을 따로 저장해두고 해당 칸을 순차적으로 채워나가는 방식이다.

채울 때의 조건은 같은 행이나 열에 그 숫자가 없고 3 x 3 칸 안에 그 숫자가 없어야 한다.

스도쿠가 다 채워지면 해당 스도쿠 답을 출력한다.

 

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

bool complete;
int zeroCnt;
int board[9][9];
pair<int, int> zero[81];

bool check(int r, int c, int n) {
	for (int i = 0; i < 9; i++)
		if (board[r][i] == n || board[i][c] == n) return false;

	for (int i = r / 3 * 3; i < r / 3 * 3 + 3; i++)
		for (int j = c / 3 * 3; j < c / 3 * 3 + 3; j++)
			if (board[i][j] == n) return false;

	return true;
}

void sudoku(int cnt) {
	if (cnt == zeroCnt) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << board[i][j];
			cout << "\n";
		}
		complete = true;
		return;
	}

	int r = zero[cnt].first;
	int c = zero[cnt].second;

	for (int i = 1; i <= 9; i++) {
		if (check(r, c, i)) {
			board[r][c] = i;
			sudoku(cnt + 1);
		}
		if (complete) return;
	}

	board[r][c] = 0;
}

int main() {
	// 입출력 속도 향상을 위함
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	string s;
	for (int i = 0; i < 9; i++) {
		cin >> s;
		for (int j = 0; j < 9; j++) {
			board[i][j] = s[j] - '0';
			if (board[i][j] == 0) zero[zeroCnt++] = { i, j };
		}
	}

	sudoku(0);
}

아래가 내가 푼 방식

위에가 12095문제에 주어진 답

시간차이가 두 배 이상이다.