[BOJ] 백준 2580번 스도쿠 c++

BOJ 문제 링크 : https://www.acmicpc.net/problem/2580

2580번: 스도쿠

스도쿠는 아래와 같은 규칙으로 빈칸을 채워나가는 게임이다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

2. 굵은 선으로 구분되어 있는 3*3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

입력될때 빈칸은 0으로 입력된다.

입력으로 스도쿠 문제가 주어졌을때 알맞게 빈칸을 채운 9*9 행렬을 출력하는 문제이다.

	#include<iostream>
	#include<vector>
	using namespace std;
	int map[9][9];
	vector<pair<int, int>> emptyBlock;
	vector<int> check(int y, int x) {
	vector<int> v;
	// 숫자들을 하나씩 대조해본다.
	for (int i = 1; i < 10; i++) {
	bool flag = false;
	for (int j = 0; j < 9; j++) {
	// 같은 행에 숫자들을 검사
	if (map[y][j] == i) {
	flag = true;
	break;
	}
	// 같은 열에 숫자들을 검사
	if (map[j][x] == i) {
	flag = true;
	break;
	}
	}
	if (flag)
	continue;
	// 같은 블락에 있는 숫자들을 검사
	int firstY = (y / 3) * 3;
	int firstX = (x / 3) * 3;
	for (int j = firstY; j < firstY + 3; j++) {
	for (int k = firstX; k < firstX + 3; k++) {
	if (map[j][k] == i) {
	flag = true;
	break;
	}
	}
	if (flag)
	break;
	}
	if (flag)
	continue;
	// 중복되는게 하나도 없으면 v에 삽입
	v.push_back(i);
	}
	return v;
	}
	bool solve(int it) {
	// 스도쿠 문제를 해결했다면 return true;
	if (it == emptyBlock.size())
	return true;
	// 다음 0인 칸을 찾는다.
	int y = emptyBlock[it].first;
	int x = emptyBlock[it].second;
	// 해당 칸에 들어갈 수 있는 숫자들을 찾는다.
	vector<int> valid = check(y, x);
	// 해당 칸에 들어갈 수 있는 수가 없다면 그 전 과정이 잘못됨
	if (valid.empty())
	return false;
	// 들어갈 수 있는 수들을 하나씩 대입
	for (int k = 0; k < valid.size(); k++) {
	map[y][x] = valid[k];
	if (solve(it + 1) == true)
	return true;
	map[y][x] = 0;
	}
	// 이전 단계의 숫자 선택이 잘못된 경우
	return false;
	}
	int main() {
	for (int i = 0; i < 9; i++) {
	for (int j = 0; j < 9; j++) {
	cin >> map[i][j];
	if (map[i][j] == 0)
	emptyBlock.push_back(make_pair(i, j));
	}
	}
	solve(0);
	for (int i = 0; i < 9; i++) {
	for (int j = 0; j < 9; j++)
	cout << map[i][j] << ' ';
	cout << endl;
	}
	}

view raw [BOJ] 백준 2580번 스도쿠.cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/BOJ/blob/main/%232580.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!