백준 2580번: 스도쿠 - DFS, 백트래킹 C++

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

2580번: 스도쿠

문제풀이코드는 맨 하단에 있습니다.

 

1.문제설명

백준 스도쿠 문제

스도쿠를 푸는 문제이다.

비어있는 칸을 채워주면 된다.

 

규칙은 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다

굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

 

문제입력

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

빈칸은 0으로 입력된다.

출력은 스도쿠로 가능한 방법 중 하나를 출력하면 된다.

 

 

2.접근방법[알고리즘]

비워있는 칸을 규칙에 따라서 채워야한다.

빈칸, 즉 스도쿠에서 입력값이 0인 좌표를 배열에 저장한다.

 

백준 스도쿠 설명

 

일단 빈칸에 들어갈 숫자는 1~9 중 하나이고

가로줄,세로줄, 3x3 정사각형 안에 이미 등장했는지 안했는지 체크해준다.

 

2-1 체크 함수

//value 사용 할 수 있는지 체크하는 함수
//리턴 값 true면 사용가능
bool check(int x, int y, int value) {
	//가로 세로에서 value 이미 존재하는지 탐색
	for (int i = 0; i < 9; i++) {
		if(arr[i][y] == value) return false;
		if (arr[x][i] == value) return false;
	}
	//3x3 칸 내에 value 이미 존재하는지 탐색
	int part_x = x / 3;
	int part_y = y / 3;
	part_x *= 3;
	part_y *= 3;
	for (int i = part_x; i < part_x + 3; i++) {
		for (int j = part_y; j < part_y + 3; j++) {
			if (arr[i][j] == value) return false;
		}
	}
	return true;
}

 

check함수를 이용해 이미 등장한 숫자가 아니라면 숫자를 넣어보고

다음 빈칸을 똑같은 과정을 수행해본다.

그리고 모든 빈칸에 숫자를 넣는다면 함수를 종료해준다.

 

그리고 정답이 나올 때까지 모든 경우에 탐색을 해봐야하므로

빈칸에 숫자를 넣고 DFS를 시행해보고 다시 그 빈칸을 초기화해주어야한다.

초기화해주지 않으면 모든 숫자가 0 인 경우에 대해서 스도쿠를 꽉 채우지 못한다.

DFS함수

void DFS(int cur) {
	if (isend == true) return;
	if (cur == L) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << arr[i][j] << ' ';
			}
			cout << '\n';
		}
		isend = true;
	}
	else{
		int nx = v[cur].first;
		int ny = v[cur].second;
		for (int i = 1; i <= 9; i++) {
			if (check(nx, ny, i)) {
				arr[nx][ny] = i;
				DFS(cur + 1);
				//위에 DFS가 정답이 아닐 수도 있으니 초기화하고 돌아줘야한다.
				arr[nx][ny] = 0;
			}
		}
	}
}

 

스도쿠 반례

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

 

 

 

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int arr[9][9], L;
vector<pair<int, int> > v;

bool isend = false;
//value 사용 할 수 있는지 체크하는 함수
//리턴 값 true면 사용가능
bool check(int x, int y, int value) {
	for (int i = 0; i < 9; i++) {
		if(arr[i][y] == value) return false;
		if (arr[x][i] == value) return false;
	}
	//3x3 칸 내에 value 이미 존재하는지 탐색
	int part_x = x / 3;
	int part_y = y / 3;
	part_x *= 3;
	part_y *= 3;
	for (int i = part_x; i < part_x + 3; i++) {
		for (int j = part_y; j < part_y + 3; j++) {
			if (arr[i][j] == value) return false;
		}
	}
	return true;
}

void DFS(int cur) {
	if (isend == true) return;
	if (cur == L) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << arr[i][j] << ' ';
			}
			cout << '\n';
		}
		isend = true;
	}
	else{
		int nx = v[cur].first;
		int ny = v[cur].second;
		for (int i = 1; i <= 9; i++) {
			if (check(nx, ny, i)) {
				arr[nx][ny] = i;
				DFS(cur + 1);
				//위에 DFS가 정답이 아닐 수도 있으니 초기화하고 돌아줘야한다.
				arr[nx][ny] = 0;
			}
		}
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 0) {
				v.push_back({ i,j });
			}
		}
	}
	L = v.size();
	DFS(0);
}

2580번 메모리 및 시간

4. 문제풀이후기

빈칸에 넣을 수 있는 숫자를 계속 넣어보면서

백트래킹을 수행하면 풀 수 있는 문제였습니다.