백준 2239번 스도쿠

링크텍스트

스도쿠가 주어지면 정답을 출력하는 프로그램을 작성해야 한다.
정답이 여러가지라면 사전식으로 가장 앞서는 것을 출력한다.

• 풀이 방법

Brute force, backtracking 방식으로 푼다.

우선 값이 0인, 즉 채워야 하는 칸들의 좌표를 vector인 zeroCells에 row가 낮은 순으로, 같다면 col이 낮은 순으로 저장한다. 이를 통해 사전식으로 가장 앞서는 것을 가장 먼저 찾게 되며, 다음 빈칸을 찾기 위한 작업을 여러번 반복하지 않을 수 있다.

func() 함수에서는 zeroCells 중 몇번째 칸을 작업할지 index를 parameter로 받는다. tryN() 함수를 호출해 해당 칸에 n이라는 숫자가 가능한지 확인하고, 가능하다면 해당 칸을 n으로 채운다. 다음 칸에 대한 작업을 진행하기 위해 func()를 재귀적으로 호출한다. Backtracking 방식을 사용하고 있으므로 함수에서 return한 후에 반드시 해당 칸을 0으로 되돌려야 한다.

index가 zeroCells의 크기에 도달하면 끝난 것이므로, 출력하고 종료한다.

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> zeroCells;

int field[9][9];
bool term = false;

bool tryN(int row, int col, int n) {
	//check 3*3 square
	int baseRow = row - row % 3;
	int baseCol = col - col % 3;

	for (int r = baseRow; r < baseRow + 3; r++) {
		for (int c = baseCol; c < baseCol + 3; c++) {
			if (field[r][c] == n) {
				return false;
			}
		}
	}

	//check vertical
	for (int c = 0; c < 9; c++) {
		if (field[row][c] == n) {
			return false;
		}
	}

	//check horizontal
	for (int r = 0; r < 9; r++) {
		if (field[r][col] == n) {
			return false;
		}
	}

	return true;
}

void func(int idx) {
	int row = zeroCells[idx].first;
	int col = zeroCells[idx].second;

	bool found = false;

	for (int n = 1; n <= 9; n++) {
		found = false;

		if (tryN(row, col, n)) {
			field[row][col] = n;

			if (zeroCells.size() - 1 == idx) {
				term = true;

				int num = 0;

				for (int r = 0; r < 9; r++) {
					num = 0;
					for (int c = 0; c < 9; c++) {
						num *= 10;
						num += field[r][c];
					}
					cout << num << endl;
				}

				return;
			}

			func(idx + 1);

			field[row][col] = 0;

			if (term) {
				return;
			}
		}
	}
}

int main(void) {
	int input;
	for (int i = 0; i < 9; i++) {
		cin >> input;
		for (int j = 8; j >= 0; j--) {
			field[i][j] = input % 10;
			input /= 10;
		}
	}

	for (int i = 0; i < 9; i++) {
		for(int j = 0; j < 9; j++){
			if (field[i][j] == 0) {
				zeroCells.push_back({ i, j });
			}
		}
	}

	//call func()
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (field[i][j] == 0) {
				func(0);
			}
		}
	}

	return 0;
}