개요

백준 2580번: 스도쿠

• 입력
  아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

• 출력
  모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

접근 방식

1. 벡터를 이용해 0인칸의 정보를 미리 저장해두었다.

   //빈칸의 정보
   struct emptySpace {
   	//빈칸의 행
   	int height;
   	//빈칸의 열
   	int width;
   };
   
   // 0인 칸 정보 미리 저장하는 벡터
   vector<emptySpace> v;

2. 그 후 백트래킹 방식으로 벡터 v의 원소(빈칸)들을 iterator을 이용해 0부터 9까지 넣을수 있는지 체크한 후 넣어주는 방식으로 채워나갔다.

   
   //백트래킹으로 스도쿠 채우는 함수
   void Backtracking(vector<emptySpace>::iterator iter,int zeroFilled) {
   
   	//0갯수가 다 채워졌다면
   	if (zeroFilled == v.size()) {
   		PrintSudoku();
   		return;
   	}
   	//iterator가 끝이면 return
   	if (iter == v.end()) return;
   
      //반복문을 통해 1부터 9까지 넣고 다음 재귀함수 호출
   	for (int i = 1; i <= 9; i++) {
          //이미 출력되었다면 return하기
   		if (PrintedAnswer) return;
   		//i값이 못 들어가면 continue
   		if (!CheckIfNumFullfillCondition(iter->height, iter->width, i)) continue;
   		//들어갈 수 있따면 sudoku값 바꾸기
   		sudoku[iter->height][iter->width] = i;
   		Backtracking(iter+1, zeroFilled + 1);
          //빠져나왔다면 다시 0으로 바꿔주기(백트래킹의 정점 초기화)
   		sudoku[iter->height][iter->width] = 0;
   	}
   }
   

   각 backtracking함수의 인자로는 어떤 빈칸을 가리키는지에 대한 iterator와
   몇개를 채워넣었는지를 뜻하는 zeroFilled를 넣어줬다.

3. 체크하는 함수로는 행과 열, 그리고 3x3구역을 체크하여
   같은 숫자가 없으면 넣을 수 있게 판단해주는 CheckIfNumFullfillCondition()함수를 구현하였다.
   3x3구역은 해당 좌표의 행값과 열값을 3으로 나눈 몫에 3을 다시 곱함으로
   해당 구역의 시작점을 알수 있다.

   /// <summary>
   /// num값이 (height,width)좌표에 들어갈 수 있는치 체크
   /// </summary>
   /// <param name="행(height)"></param>
   /// <param name="열(width)"></param>
   /// <param name="num"></param>
   /// <returns>좌표에 들어간다면 true 못 들어가면 false</returns>
   bool CheckIfNumFullfillCondition(int height, int width, int num) {
   	for (int i = 0; i < 9; i++) {
   		//행에 중복되는 숫자가 있다면 return false
   		if (sudoku[height][i] == num) return false;
   		//열에 중복되는 숫자가 있다면 return false
   		if (sudoku[i][width] == num) return false;
   	}
   	//해당칸의 3x3구역 중복된거 있는지 체크
   	for (int i = (height / 3) *3; i < (height / 3)*3 + 3; i++) {
   		for (int j = (width / 3)*3 ; j < (width / 3)*3 + 3; j++) {
   			if (sudoku[i][j] == num) return false;
   		}
   	}
      //중복된게 없다면 return true
   	return true;
   }
   

4. 만약 다 채워넣었다면 스도쿠를 printSudoku()함수를 통해 출력해준 후,
   bool형 변수 PrintedAnswer을 true로 변환하여 반복되는 백트래킹에서 빠져나오게 하였다.

   //sudoku프린트하는 함수
   void PrintSudoku() {
   	cout << '\n';
   	for (int i = 0; i < 9; i++) {
   		for (int j = 0; j < 9; j++) {
   			cout << sudoku[i][j]<<" ";
   		}
   		cout << '\n';
   	}
   	PrintedAnswer = true;
   }

코드

#include<iostream>
#include<vector>

using namespace std;
//입력값 받는 배열
int sudoku[9][9];

//답 출력했다면 바로 재귀 다 끊을 수 있도록
bool PrintedAnswer = false;

//빈칸의 정보
struct emptySpace {
	//빈칸의 행
	int height;
	//빈칸의 열
	int width;
};

// 0인 칸 정보 미리 저장하는 벡터
vector<emptySpace> v;


void Input() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> sudoku[i][j];
            //0이면 벡터에 푸시
			if (sudoku[i][j] == 0) 
			    v.push_back({ i,j});
		}
	}
}


/// <summary>
/// num값이 (height,width)좌표에 들어갈 수 있는치 체크
/// </summary>
/// <param name="행(height)"></param>
/// <param name="열(width)"></param>
/// <param name="num"></param>
/// <returns>좌표에 들어간다면 true 못 들어가면 false</returns>
bool CheckIfNumFullfillCondition(int height, int width, int num) {
	for (int i = 0; i < 9; i++) {
		//행에 중복되는 숫자가 있다면 return false
		if (sudoku[height][i] == num) return false;
		//열에 중복되는 숫자가 있다면 return false
		if (sudoku[i][width] == num) return false;
	}
	//해당칸의 3x3구역 중복된거 있는지 체크
	for (int i = (height / 3) *3; i < (height / 3)*3 + 3; i++) {
		for (int j = (width / 3)*3 ; j < (width / 3)*3 + 3; j++) {
			if (sudoku[i][j] == num) return false;
		}
	}
    //중복된게 없다면 return true
	return true;
}

//sudoku프린트하는 함수
void PrintSudoku() {
	cout << '\n';
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << sudoku[i][j]<<" ";
		}
		cout << '\n';
	}
	PrintedAnswer = true;
}

//백트래킹으로 스도쿠 채우는 함수
void Backtracking(vector<emptySpace>::iterator iter,int zeroFilled) {

	//0갯수가 다 채워졌다면
	if (zeroFilled == v.size()) {
		PrintSudoku();
		return;
	}
	//iterator가 끝이면 return
	if (iter == v.end()) return;

    //반복문을 통해 1부터 9까지 넣고 다음 재귀함수 호출
	for (int i = 1; i <= 9; i++) {
        //이미 출력되었다면 return하기
		if (PrintedAnswer) return;
		//i값이 못 들어가면 continue
		if (!CheckIfNumFullfillCondition(iter->height, iter->width, i)) continue;
		//들어갈 수 있따면 sudoku값 바꾸기
		sudoku[iter->height][iter->width] = i;
		Backtracking(iter+1, zeroFilled + 1);
        //빠져나왔다면 다시 0으로 바꿔주기(백트래킹의 정점 초기화)
		sudoku[iter->height][iter->width] = 0;
	}
}


void Solution() {
	auto iter = v.begin();
	Backtracking(iter, 0);
}

int main() {
	Input();
	Solution();
}

문풀후생

1. 시간을 더 단축시켜보려고 입력받는 과정에서 행,열,3x3구역을 다 확인해서
   나머지 8구역이 다 차서 확정이면 해당 값을 미리 저장하고 백트래킹을 해보려했다.
   하지만 막상 구현해보고 위의 코드와 백준 시간차이를 비교해보니 거의 차이가 안나는 수준이었다.
   시간차이도 많이 안 나고 가독성도 더 떨어져서 그냥 위의 코드로 진행하였다.