[c++] 백준-스도쿠 1520 - 백트래킹

1. 문제

2. 입출력

3. 예제 입 출력

4. 문제 해설

우리가 흔히 알고 있는 스도쿠 문제를 백트래킹을 이용해서 푸는 문제였다. 생각해보면 우리가 스도쿠를 푸는 과정도 백트래킹과 같다. 

내가 문제를 푼 과정은 다음과 같다. 

 

1. 입력을 받는다. 
   1. rows라는 2차원 배열에 각 행마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. 
   2. cols라는 2차원 배열에  각 열마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. 
   3. square라는 2차원 배열에 각각의 작은 4각형마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. 
   4. vector에 0에 해당하는(우리가 구해야하는) 좌표를 저장해주었다.
2. 깊이 우선탐색을 이용한다. 
   1. 깊이 우선 탐색을 이용해 1 ~ 9까지 순서대로 그 칸에 해당하는 rows배열과 cols배열 square배열을 검사한 후 들어갈 수 있는 숫자를 집어 넣는다. 
   2. 만약 아무것도 집어넣을 수 없는 상황이 온다면 함수를 return 해주는데 리턴하면서 집어넣었던 rows배열과 cols배열 square배열의 i를 다시 0으로(아직 나오지 않음)으로 변경해준다. -> 백트래킹
   3. 만약 현재 탐색하고 있는 index가 아까 0들의 좌표를 집어넣은 vector의 사이즈와 같아진다면 puzzle배열을 출력하고 return 한다.

백트래킹은 함수가 재귀함수와 함수 return 후의 동작이 중요하다. 

DFS를 통해 스도쿠 배열을 탐색하면서 만약 들어갈 수 있는 숫자가 있다면 그 숫자를 넣어주고 rows배열과 cols배열 square배열에 방문 표시를 해준다. 그 후 더 이상 갈 수 없다면 지금까지 채워온 숫자들이 답이 아니라는 뜻인데 그렇다면 다시 체크하면서 진행했던 숫자들을 다시 원상태로 돌려주면서 다시 탐색해야한다. 따라서 백트래킹을 이용하는 문제였다. 

 

나는

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

다음과 같이 정사각형을 나눴기 때문에 정사각형에 해당하는 인덱스는 

 

square[((i /3) *3) + j/3)][x]로 지정해줬다. 

 

4. 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <vector>
using namespace std;

int puzzle[10][10];
bool rows[10][10];
bool cols[10][10];
bool square[9][10];
//3가지의 방문 배열을 체크해야함 
vector<pair<int, int>> zeros;
void input() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			scanf("%d", &puzzle[i][j]);
			if (puzzle[i][j] == 0) zeros.push_back({ i,j }); //구해야하는 좌표 저장
			rows[i][puzzle[i][j]] = 1;
			cols[j][puzzle[i][j]] = 1;
			int squarenum = ((i / 3) * 3) + (j / 3);
			square[((i / 3) * 3) + (j / 3)][puzzle[i][j]] = 1; // 4각형 안의 방문 표시
		} //입력을 받는다. 
	}
}
int cnt;
void BackTrack(int idx) {
	if (idx == zeros.size() && cnt == 0) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				printf("%d ", puzzle[i][j]);
			}
			printf("\n");
		}
		cnt++;
		idx--;
		return;
	}
	if (idx == zeros.size()) return;
		int squarenum = ((zeros[idx].first / 3) * 3) + (zeros[idx].second / 3);
		int ny = zeros[idx].first;
		int nx = zeros[idx].second;
		for (int i = 1; i <= 9; i++) {
			if (rows[ny][i] == 1) continue;
			if (cols[nx][i] == 1)continue;
			if (square[squarenum][i] == 1)continue;
			// 방문 배열들 체크
			puzzle[ny][nx] = i;// 다 통과된 i를 집어 넣는다.
			rows[ny][i] = 1;
			cols[nx][i] = 1;
			square[squarenum][i] = 1;
			BackTrack(idx + 1);
			rows[ny][i] = 0;
			cols[nx][i] = 0;
			square[squarenum][i] = 0;
		}
		return;
}
int main() {
	input();

	BackTrack(0);
	return 0;
}

처음에는 cnt라는 전역 변수 없이 출력을 했었는데 경우가 많은 경우 여러번 출력이 되어 답이 틀렸었다. 그 후 다음과 같이 cnt변수를 추가해 출력을 한 번만 해주니 답이 맞았다.