C++ / 백준 / 2580 / 스도쿠

문제

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

2580번: 스도쿠

문제풀이

0인 좌표를 큐에 넣고 숫자를 넣었으면 큐에서 pop 하는 식으로 풀었는데 숫자가 안 채워지는 부분이 있어 틀렸다.

다른 블로그를 참고해서 풀었다.

문제풀이는 모든 경우의 수를 탐색하고, 숫자가 채워졌으면 다음 0인 칸으로 가서 다시 숫자를 채운다.

다음 칸에서 9까지 확인을 했는데 다른 부분과 겹쳐 채워질 수 없으면 다시 전 칸으로 돌아와 다른 숫자로 채운다.

이런 식으로 모든 경우의 수를 확인하고 모든 칸이 채워졌을 때 스도쿠판을 출력하면 된다.

 

vector<pair<int, int>zero를 선언하여 0을 입력받으면 zero에 y, x좌표를 넣는다.

		for (row = 0; row < 9; ++row)
			if (board[y][row] == num && row != x) {
				board[y][x] = 0;
				break;
			}

가로에 숫자가 겹치는지 확인하는 부분이다.

 

		for (col = 0; col < 9; ++col)
			if (board[col][x] == num && col != y) {
				board[y][x] = 0;
				break;
			}

세로에 숫자가 겹치는지 확인하는 부분이다.

 

		for (col = y / 3 * 3; col < y / 3 * 3 + 3; ++col)
			for (row = x / 3 * 3; row < x / 3 * 3 + 3; ++row)
				if (board[col][row] == num && col != y && row != x) {
					board[y][x] = 0;
					break;
				}

3x3칸에서 숫자가 겹치는지 확인하는 부분이다.

y가 5라면 3, 4, 5인 곳을 확인해야 하므로 3으로 나누고 다시 3을 곱해 0, 3, 6인 곳부터 각각 2, 5, 8인 곳까지 확인하게 해 주었다.

만약 숫자가 겹친다면 다시 0으로 바꾸고 num값을 늘려 다시 처음부터 판별한다.

 

		if (board[y][x] != 0) {
			if (idx == zero.size() - 1) {
				for (col = 0; col < 9; ++col) {
					for (row = 0; row < 9; ++row)
						cout << board[col][row] << ' ';
					cout << '\n';
				}
				exit(0);
			}
			else check(zero[idx + 1].first, zero[idx + 1].second, idx + 1);
		}

세 가지 조건을 확인하고 다른 부분과 숫자가 겹치지 않는다면 다시  확인한다.

0인 부분을 모두 확인했으면 보드가 완성된 것이므로 출력을 하고 exit를 통해 프로그램을 종료한다.

아직 0인 부분이 남아있으면 idx를 늘려 다음 0인 칸을 확인하도록 한다.

 

	board[y][x] = 0;

num이 9인데도 이 부분에 도착했다면 이전 칸들을 다시 채워야 한다는 의미이다.

이 명령어를 채우지 않는다면 몇몇 반례에서 다른 숫자로 채워지지 않는 부분이 발생한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>>board(9, vector<int>(9, 0));
vector<bool>number(10, false);
vector<pair<int, int>>zero;

void check(int y, int x, int idx) {
	int num(0);
	int row(0), col(0);
	for (num = 1; num <= 9; ++num) {
		board[y][x] = num;
		for (row = 0; row < 9; ++row)
			if (board[y][row] == num && row != x) {
				board[y][x] = 0;
				break;
			}
		for (col = 0; col < 9; ++col)
			if (board[col][x] == num && col != y) {
				board[y][x] = 0;
				break;
			}
		for (col = y / 3 * 3; col < y / 3 * 3 + 3; ++col)
			for (row = x / 3 * 3; row < x / 3 * 3 + 3; ++row)
				if (board[col][row] == num && col != y && row != x) {
					board[y][x] = 0;
					break;
				}

		if (board[y][x] != 0) {
			if (idx == zero.size() - 1) {
				for (col = 0; col < 9; ++col) {
					for (row = 0; row < 9; ++row)
						cout << board[col][row] << ' ';
					cout << '\n';
				}
				exit(0);
			}
			else check(zero[idx + 1].first, zero[idx + 1].second, idx + 1);
		}
	}	
	board[y][x] = 0;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int y(0), x(0);

	for (y = 0; y < 9; ++y)
		for (x = 0; x < 9; ++x) {
			cin >> board[y][x];
			if (board[y][x] == 0)
				zero.push_back({ y,x });
		}

	check(zero[0].first, zero[0].second, 0);
}