[백준] 2580번 - 스도쿠

 

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

2580번: 스도쿠

💡 스도쿠란?

스도쿠는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 숫자넣기로도 불린다. “숫자는 한 번씩만 쓸 수 있다”(数字は独身に限る 수'지와 독'신'니가길[*])[1]를 줄인 말로 2005년 전 세계적으로 이 말과 퍼즐이 퍼져나갔다. 퍼즐을 푸는 방법은 아홉 가로줄, 세로줄, 3X3 칸에 1에서 9까지의 숫자를 중복되지 않게 한 번씩만 넣으면 된다.

 

따라서 0으로 된 숫자에 가로, 세로, 3X3 칸에 1~9까지의 숫자 중 하나를 중복되지 않게 넣어줘야 하는 문제이다.

 

처음에는 가로로 한 줄씩 가져와 0으로 된 곳에 1~9까지 어떤 수가 들어 갈 수 있는지 파악한 후,

가능한 수열을 만든 후 나머지 세로, 3X3을 확인해보는 방법으로 접근했었다.

 

하지만 이 방법은 시간이 턱 없이 부족했었다. 

 

그 후 생각을 하다, 줄에 상관없이 처음의 0부터 백트래킹 방식으로 그때 그때 가로, 세로, 3X3의 조건을 확인해가며  1~9를 넣어보며 푸는 방식을 생각해내 코드를 구현하게 되었다.

 

그래서 스도쿠 내 0인 곳의 인덱스를 저장해주는 visited 배열을 만들어 저장을 해준 후

check1, check2, check3를 이용해 1~9까지 넣어가며 조건에 맞으면 다음 0인 곳을, 아니면 1~9의 다른 수를 넣어봤다.

✏️ 구현

check1 : 0의 인덱스 기준 가로에 있는 숫자 1~9 여부 배열

check2 : 0의 인덱스 기준 세로에 있는 숫자 1~9 여부 배열

for (int j = 0; j < 9; ++j) 
{
	check1[arr[visited[idx].first][j]] = true;
	check2[arr[j][visited[idx].second]] = true;
}

 

check3 : 0의 인덱스 기준 세로에 있는 숫자 1~9 여부 배열 

for (int j = (visited[idx].first / 3) * 3; j < ((visited[idx].first / 3) * 3) + 3; j++) {
	for (int k = (visited[idx].second / 3) * 3; k < ((visited[idx].second / 3) * 3) + 3; k++) {
			check3[arr[j][k]] = true;
	}
}

0의 위치(x,y)의 3X3 부분의 1~9 여부를 구하기 위해서 3X3인 배열의 가장 위의 왼쪽 부분을 구한 후 for문을 만들었다.

가장 위의 왼쪽 인덱스 -> first_x = (x/3)*3 , first_y = (y/3)*3

이렇게 해준 후 0의 개수가 점점 줄어 cnt가 0이 되면 그때의 arr값을 반환해주면 된다.

※ 여러 개의 닶이 존재할 때 하나만 출력 할 수 있도록 flag를 사용해 하나 출력 후 더 이상 dfs를 실행시키지 않도록 해주자!

 

📃 구현 코드 :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> arr;
vector<pair<int, int>> visited;
bool flag = true;
int tmp_cnt;
void dfs(int cnt) {
	if (cnt == 0) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				cout << arr[i][j] << " ";
			}
			cout << endl;
		}
		flag = false;
	}
	else {
		if (flag) {
			int idx = tmp_cnt - cnt;
			vector<bool> check1 = vector<bool>(10, false);
			vector<bool> check2 = vector<bool>(10, false);
			vector<bool> check3 = vector<bool>(10, false);

			for (int j = 0; j < 9; ++j) {
				check1[arr[visited[idx].first][j]] = true;
				check2[arr[j][visited[idx].second]] = true;
			}

			for (int j = (visited[idx].first / 3) * 3; j < ((visited[idx].first / 3) * 3) + 3; j++) {
				for (int k = (visited[idx].second / 3) * 3; k < ((visited[idx].second / 3) * 3) + 3; k++) {
					check3[arr[j][k]] = true;
				}
			}

			for (int i = 1; i <= 9; ++i) {
				if (!check1[i] && !check2[i] && !check3[i]) {
					check1[i] = true;
					check2[i] = true;
					check3[i] = true;

					arr[visited[idx].first][visited[idx].second] = i;

					dfs(cnt - 1);

					arr[visited[idx].first][visited[idx].second] = 0;
					check1[i] = false;
					check2[i] = false;
					check3[i] = false;
				}
			}



		}
	}
	
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	arr = vector<vector<int>>(9, vector<int>(9, 0));
	int cnt = 0;
	
	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			cin >> arr[i][j];
			if (arr[i][j] == 0) {
				cnt++;
				visited.push_back(make_pair(i, j));
			}
		}
	}

	tmp_cnt = cnt;
	dfs(cnt);

}

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!