[백준]No.2580 - 스도쿠 (C++)

문제

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

2580번: 스도쿠

풀이

실제로 스도쿠 문제를 풀때, 가능한 수 중에 한개씩 넣어보면서 진행하다 불가능할 경우 뒤로 돌아가서 수를 바꾸는데 말그대로 백트래킹이 적용 가능한 문제이다.

 

입력 받은 스도쿠 배열에서 다음 0을 찾아 nr,nc에 저장한 후, pos_num에 행,열과 해당 3x3 범위의 수들을 확인하여 간능한 수를 찾아준다.

그 다음은 가능한 수를 for문으로 넣어보면서 재귀호출을 하면, 마지막 0에서 답을 찾은 경우 board[][]를 출력해주면 된다.

코드

	#include <iostream>
	#include <string.h>
	using namespace std;
	int board[9][9];
	bool printed = false; //전체 재귀의 종료 여부
	void PrintBoard(){
	for(int i=0; i<9 ; ++i){
	for(int j=0; j<9 ; ++j){
	cout<<board[i][j]<<' ';
	}
	cout<<'\n';
	}
	return;
	}
	void SdocuCheck(int r,int c){
	int nr,nc;
	bool check_next = false; //다음으로 나오는 0을 확인
	bool last =false; //마지막 0임을 확인
	for(int i=r; i<9 ; ++i){
	for(int j=0; j<9 ; ++j){
	if(i==r && j==c)
	continue;
	if(board[i][j] ==0){
	nr = i;
	nc = j;
	check_next = true; //0확인시 for문 탈출
	break;
	}
	}
	if(check_next)
	break;
	if(i==8){ //0이 더이상 없는 경우 해결한 것
	last =true;
	break;
	}
	}
	bool pos_num[10];
	memset(pos_num, true , sizeof(pos_num));
	for(int i=0; i<9 ; ++i)
	pos_num[board[r][i]] = false; //같은 행에 나온 수는 false 로
	for(int i=0; i<9 ; ++i)
	pos_num[board[i][c]] = false;//같은 열에 나온 수는 false 로
	int start_r, start_c, end_r,end_c;
	start_r = 3*(r/3);
	start_c = 3*(c/3);
	end_r = start_r +3;
	end_c = start_c +3;
	for(int i= start_r; i<end_r ; ++i){
	for(int j=start_c; j<end_c ; ++j){
	pos_num[board[i][j]] = false; //같은 정사각 칸에 나오는 수 false
	}
	}
	for(int i=1; i<10 ; ++i){
	if(printed)
	return;
	if(pos_num[i]){
	if(last){
	board[r][c] = i;
	PrintBoard(); //마지막칸 이므로 스도쿠 답을 출력 후
	printed = true; // 전체 재귀를 종료시킴
	return;
	}
	board[r][c] = i;
	SdocuCheck(nr,nc);
	}
	}
	board[r][c] = 0;//다시 돌려줌
	}
	int main(){
	int fr,fc;
	bool check_first =false;
	for(int i=0; i<9 ; ++i)
	for(int j=0; j<9 ; ++j)
	cin>>board[i][j];
	for(int i=0; i<9 ; ++i){
	for(int j=0; j<9 ; ++j){
	if(board[i][j]==0){
	fr=i;
	fc=j;
	check_first =true;
	break;
	}
	}
	if(check_first)
	break;
	}
	SdocuCheck(fr,fc); //처음으로 나오는 0을 확인해 함수 호출
	return 0;
	}

view raw 스도쿠.cpp hosted with ❤ by GitHub