백준 2580번 스도쿠

< 백준 2580번 스도쿠 - 마포 코딩박 >

사용한 알고리즘: DFS


 9*9 grid 의 스도쿠의 빈칸을 채우는 문제였습니다.
 DFS 를 통해 빈칸을 채워보아 문제를 해결했습니다,

문제풀이 과정은 다음과 같습니다.
(1)
 기본적으로 (i,j) 칸에 k라는 숫자가 들어가려면, i row 와 j column, 그리고 (i,j) 가 위치한 3*3 사각형( (i/3)*3+(j/3) 번째 사각형 ) 안에 k 가 없어야 합니다.

(1) (코드: 40~51)
 각 grid를 입력받으며 해당 숫자를 배열(arr)에 저장해주었습니다. row, col, square 에 해당 숫자가 있음을 저장해주었습니다. 빈칸이 입력되면 이를 따로 pair형태로 저장해주었습니다.

(2) (코드: 10~15)
 (x,y) 칸에 숫자 num 이 들어갈 수 있는지 확인하는 함수를 만들어 줍니다.

(3) (코드: 16~38)
 빈칸을 순서대로 둘러보며, 각 빈칸에 1~9 중 가능한 숫자를 넣어보는 DFS 를 돌렸습니다.
각 빈칸에 k 숫자를 넣어줄 때 row, col, square 도 업데이트 해주어야합니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef pair<int, int> pii;
	int number, arr[9][9];
	set<int> Square[9], row[9], col[9];
	vector<pii> HaveToChange;
	// x,y 칸에 num을 넣는게 가능한지 확인
	bool Possi(int x, int y, int num){
	if(Square[(x/3)*3+(y/3)].count(num)) return false;
	if(row[x].count(num)) return false;
	if(col[y].count(num)) return false;
	return true;
	}
	bool DFS(int idx, int cnt){
	// 바꾼 개수(cnt) = 비어있는 개수(number) 이면 DFS를 끝냄
	if(idx>=HaveToChange.size() && cnt==number) return true;
	pii now = HaveToChange[idx];
	// idx번째 빈칸에 1~9 중 들어갈 수 있는 숫자 넣어보기
	for (int k = 1; k <= 9; ++k){
	if(Possi(now.first,now.second,k)){
	arr[now.first][now.second] = k;
	// Square, row, col 업데이트
	Square[(now.first/3)*3+(now.second/3)].insert(k);
	row[now.first].insert(k);
	col[now.second].insert(k);
	// idx번째 빈칸을 k로 바꾼 후 DFS 돌려서, 비어있는 칸을 다 채울 수 있으면 DFS 끝냄
	if(DFS(idx+1,cnt+1)) return true;
	// 여기로 내려온거면 idx번째 빈칸을 k로 바꿨을 때 다른 빈칸들을 다 채울 수 없는 거
	// idx번째 빈칸에 k 넣었던거 빼서 원상복구
	Square[(now.first/3)*3+(now.second/3)].erase(k);
	row[now.first].erase(k);
	col[now.second].erase(k);
	}
	}
	return false;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	for (int i = 0; i < 9; ++i){
	for (int j = 0; j < 9; ++j){
	cin >> arr[i][j];
	Square[(i/3)*3+(j/3)].insert(arr[i][j]);
	row[i].insert(arr[i][j]);
	col[j].insert(arr[i][j]);
	if(arr[i][j]==0){
	number++;
	HaveToChange.push_back(pii(i,j));
	}
	}
	}
	DFS(0,0);
	for (int i = 0; i < 9; ++i){
	for (int j = 0; j < 9; ++j){
	cout << arr[i][j] << ' ';
	}
	cout << '\n';
	}
	return 0;
	}

view raw BOJ 2580.cpp hosted with ❤ by GitHub