[BAECKJOON] 2580번 스도쿠

문 제

소 스  코 드

#include <iostream>
#include <vector>

constexpr int MAX_BOARD			{ 9 };
constexpr int SUDOKU_EMPTY		{ 0 };


void Func(const int&);
bool Is_Exist(const int&, const int&);
void Display();

int sudoku_board[MAX_BOARD][MAX_BOARD];
std::vector<std::pair<int, int>> sudoku;
bool finish{ false };

int main() {
	// reserver vector
	sudoku.reserve(MAX_BOARD * MAX_BOARD);

	// input & search 0 index
	for (int y = 0; y < MAX_BOARD; ++y) {
		for (int x = 0; x < MAX_BOARD; ++x) {
			std::cin >> sudoku_board[y][x];

			if(SUDOKU_EMPTY == sudoku_board[y][x])sudoku.emplace_back(std::make_pair(y, x));

		}
	}

	Func(0);

	return 0;
}

void Display() {
	std::cout << '\n';
	for (int y = 0; y < MAX_BOARD; ++y) {
		for (int x = 0; x < MAX_BOARD; ++x) {
			std::cout << sudoku_board[y][x]<< " ";

		}
		std::cout << '\n';
	}
}

bool Is_Exist(const int& length, const int& idx) {
	int board_first = (sudoku[length].first / 3) * 3;
	int board_second = (sudoku[length].second / 3) * 3;

	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (idx == sudoku_board[i + board_first][j + board_second])		return false;
		}
	}
	for (int i = 0; i < MAX_BOARD; ++i) {
		if (idx == sudoku_board[sudoku[length].first][i])				return false; 
		if (idx == sudoku_board[i][sudoku[length].second])				return false;

	}
	return true;
}

void Func(const int& length) {
	if (true == finish) return;
	if (length == sudoku.size()) {
		finish = true;
		Display();
		return;
	}

	for (int i = 1; i < MAX_BOARD + 1; ++i) {
		if (false == Is_Exist(length, i)) continue;
		sudoku_board[sudoku[length].first][sudoku[length].second] = i;
		Func(length + 1);
		sudoku_board[sudoku[length].first][sudoku[length].second] = 0;
	}
	return;
}

 

풀 이

• 0을 가지고 있는 위치 배열의 x, y를 알아야 한다!
  vector와 pair<>를 통해 이를 추가 관리 한다.
• 한 곳에 있을 수 있는 숫자는 1 ~ 9 이다.
• vector에 담겨 있는 모든 값을 순회하여 각 숫자에 따라 재귀 호출을 통해 진행하며 수정하며 반복한다.

 

실 수 한  사 항

• exit(1)로 프로그램을 끝내려고 하면 런타임 오류가 발생한다.

 

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] https://www.acmicpc.net/problem/2580