[백준OJ] 2239번 스도쿠

www.acmicpc.net/problem/2239

2239번: 스도쿠

---

-풀이-

1.먼저 해당 행,렬,박스에서 1~9까지 숫자중 어떤 숫자를 사용했는지 체크해주는 boolean 배열을 선언해준다.

=>bool row[9][10], col[9][10], box[9][10];

 

2.입력을 받을 때, 0이라면 0의 포지션을 저장해주는 벡터에 push_back을 해주고, 아니라면 해당 행,렬,박스에서 숫자를 사용했다고 체크를 해준다.

 

3. zero의 인덱스를 저장하는 벡터를 돌며, 1~9중 해당 인덱스를 포함하는 행,렬,박스에서 모두 사용하지않은 숫자를 넣어준뒤,다음 dfs를 돌린다.

 

4.만약 zero벡터를 끝까지 갔다면 , 위에서부터 차례대로 탐색을 했고, 1~9순서로 탐색을 했으니 최초로 완성을 한 배열이 정답이 된다. 따라서 끝까지 갔다면 정답이므로 더이상 하지않기위해 로직을 설정해준다.

 

5.만약 그 길이 아니라면 해당 인덱스에 그 숫자는 아니란 소리이므로 백트래킹을 해준뒤, 조건에 해당하는 다음 숫자를 찾아 dfs를 실행해준다

 

-코드-

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool row[9][10], col[9][10], box[9][10];
char maze[9][9];
bool flag = false;
vector<pair<int,int>> zero;
int getBox(int i, int j) {
	if (i < 3) {
		if (j < 3) {
			return 0;
		}
		else if (j < 6) {
			return 1;
		}
		else {
			return 2;
		}
	}
	else if (i < 6) {
		if (j < 3) {
			return 3;
		}
		else if (j < 6) {
			return 4;
		}
		else {
			return 5;
		}
	}
	else {
		if (j < 3) {
			return 6;
		}
		else if (j < 6) {
			return 7;
		}
		else {
			return 8;
		}
	}
}

void input() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> maze[i][j];
			if (maze[i][j] != '0') {
				row[i][maze[i][j] - '0'] = true;
				col[j][maze[i][j] - '0'] = true;
				int b = getBox(i, j);
				box[b][maze[i][j] - '0'] = true;
			}
			else {
				zero.push_back({ i,j });
			}
		}
	}
}

void dfs(int ind) {
	if (ind == zero.size()) {
		flag = true;
		return;
	}

	int x = zero[ind].first;
	int y = zero[ind].second;
	int b = getBox(x, y);
	for (int i = 1; i <= 9; i++) {
		if (!row[x][i] && !col[y][i] && !box[b][i]) {
			maze[x][y] = i + '0';
			row[x][i] = col[y][i] = box[b][i] = true;
			dfs(ind + 1);
			if (flag) {
				return;
			}
			maze[x][y] ='0';
			row[x][i] = col[y][i] = box[b][i] = false;
		}
	}
}

void solve() {
	dfs(0);
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << maze[i][j] ;
		}
		cout << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	input();
	solve();
}