백준 알고리즘 2580번 문제 : 스도쿠

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

2580번: 스도쿠

문제는 백준 알고리즘 사이트에서 확인하세요

 

오늘 포스팅할 문제는 스도쿠 문제입니다 

 

초등학생때 한번씩 풀어보셨죠?? 

 

규칙은 간단합니다

 

1. 좌우에 1부터 9까지의 숫자가 모두 한번씩만 들어가야 합니다
2. 위아래에 1부터 9까지의 숫자가 모두 한번씩만 들어가야 합니다
3. 9*9 배열을 9 등분한 구역에 1부터 9까지가 모두 한번씩만 들어가야합니다.

3번은 이런식으로요~

1	2	3
4	5	6
7	8	9

문제가 원하는 것은 0으로 채워진 스도쿠판에 들어갈 숫자를 채우는거네요~

 

1	3	5	4	6	9	2	7	8
7	8	2	1	3	5	6	4	9
4	6	9	2	7	8	1	3	5
3	2	1	5	4	6	8	9	7
8	7	4	9	1	3	5	2	6
5	9	6	8	2	7	4	1	3
9	1	7	6	5	2	3	8	4
6	4	3	7	8	1	9	5	2
2	5	8	3	9	4	7	6	1

문제의 예제를 한번 풀어봤어요. 스도쿠 재미있군요!

 

문제를 풀면서 고려해야할게 상당히 많았습니다.ㅋㅋ

 

위의 예제는 친절하게도 한가지 경우의 수 밖에 나오지 않도록 했지만

 

다른 예제의 경우 답이 여러개인 스도쿠도 있었거든요! ㅋㅋ

 

이렇게 고려해야할게 너무 많아서 계산이 복잡해질때 Backtracking 기법을 사용합니다!

 

Backtracking은 모든 경우의 수를 현명하게 선택하는 알고리즘이에요.

 

모든 경우의 수를 고려한다면 이 때의 시간 복잡도는 n!만큼 걸리게 되고...

 

INPUT이 40개만 되어도 40!(=40*39*38*...*1)이라는 어마어마한 계산을 하게됩니다.

 

INPUT이 100개를 넘어서면 아마 잠자고 일어나도 결과가 나오지 않는.. !! 사태가 벌어질 수 있습니다 ㅋㅋㅋ

 

이 어마어마한 계산량을 줄인다면 백트래킹은 많은 입력값에 대해 다른 기법보다 상당한 효율을 갖습니다.

 

어떻게 줄일 수 있을까요? 바로 promising function을 사용합니다.

 

backtracking에 대한 학술적인 내용은 wikipedia나 책을 참고하시길 바랍니다.

 

https://en.wikipedia.org/wiki/Backtracking

Backtracking - Wikipedia

백트레킹을 하기위한 준비물은 함수 2개 입니다.

 

• void sudoku()
• bool promising()

백트래킹의 효율을 높이기 위해 promising한 계산에 대해서만 sudoku를 하면 무난히..(영원히 실행되지 않고) 해결할 수 있습니다!

 

sudoku(i : 스도쿠의 칸 위치){

 if(promising(i)){

  if(모든 빈칸에 숫자를 채워넣었다면){

   종료

  }

  sudoku(i+1);// 다음칸을 방문

 }

}

 

promising(int i){

  i칸에 적은 숫자가 문제의 조건을 만족하면 true, 아니면 false

}

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

void sudoku(int i, int j);
bool promising(int i, int j);

vector<vector<int>> M;

int main() {
	M = vector<vector<int>>(9 + 1, vector<int>(9 + 1, 0));
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			cin >> M[i][j];
			if (M[i][j] < 0 || M[i][j]>9) {
				return 0;
			}
		}
	}
	sudoku(1, 0);

}

void sudoku(int i, int j) {
	if (promising(i,j)) {
		if (i == 9 && j == 9) {
			for (int n = 1; n <= i; n++) {
				for (int m = 1; m <= j; m++) {
					cout << M[n][m] << " ";
				}
				cout << endl;
			}
			exit(0);
		}
		if (j == 9) {
			i++;
			j = 0;
		}
		if (M[i][j + 1] == 0) {
			for (int k = 1; k <= 9; k++) {
				M[i][j + 1] = k;
				sudoku(i, j + 1);
			}
			/* ´Ù ½ÇÆÐÇÑ °æ¿ì */
			M[i][j + 1] = 0;
		}
		else {
			sudoku(i, j + 1);
		}
		
	}
}

bool promising(int i, int j) {
	bool promise = true;
	int rect = 1;
	int ri = 1 + ((i - 1) / 3)*3;
	int rj = 1 + ((j - 1) / 3)*3;

	if (i == 0 || j == 0) {
		return promise;
	}
	while (promise && rect<=9) {
		if (j!= rect && M[i][j] == M[i][rect]) {
			promise = false;
		}
		if (i != rect && M[i][j] == M[rect][j]) {
			promise = false;
		}
		if (i != ri && j != rj && M[i][j] == M[ri][rj]) {
			promise = false;
		}
		if (rj % 3 == 0) {
			ri++;
			rj = 1 + ((j - 1) / 3) * 3;
		}
		else {
			rj++;
		}
		rect++;
	}
	return promise;
}