[C++] 백준 2580 : 스도쿠

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

2580번: 스도쿠

백준 2580번 스도쿠를 풀어봤습니다.

비어있는 곳을 벡터에 넣어서 백트래킹 함수에서 사용했습니다.

isPromising함수에서 같은 열, 같은 행, 같은 구역인지 체크하고 promising하면 true를 넘겨줬습니다.

 

아래는 전체 코드입니다.

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

int board[9][9];
vector<pair<int, int>> v;

bool isPromising(int x,int y) {
	for (int i = 0; i < 9; i++) {
		if (board[x][i] == board[x][y] && i != y)
			return false;
		if (board[i][y] == board[x][y] && i != x)
			return false;
	}

	int tx = x / 3;
	int ty = y / 3;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (x == tx * 3 + i && y == ty * 3 + j)
				continue;

			if ((board[i + tx * 3][j + ty * 3] == board[x][y]))
				return false;
		}
	}

	return true;
}

void sudoku(int level) {
	if (level == v.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << board[i][j] << ' ';
			}
			cout << '\n';
		}
		exit(0);
		return;
	}

	int x = v[level].first;
	int y = v[level].second;

	for (int i = 0; i < 9; i++) {
		board[x][y] = i + 1;
		if (isPromising(x, y)) {
			sudoku(level + 1);
			
		}
		board[x][y] = 0;
	}
}

int main() {
	int temp;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> temp;
			board[i][j] = temp;
			if (temp == 0) {
				v.push_back({ i,j });
			}
		}
	}

	sudoku(0);

	return 0;
}