[백준 2239번 C/C++] 스도쿠

 

[백준 2239번 C/C++] 스도쿠

 

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

2239번: 스도쿠

---

 

해결전략

 

백트래킹 Backtracking

 

---

 

정답코드

 

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

vector<vector<int>> v(9, vector<int>(9));
vector<pair<int, int>> zero; // 빈 칸의 위치를 저장하는 벡터

bool isPossible(int y, int x, int select)
{
	// (y, x)에 select 숫자를 놓을때 해당 행과 열에 select과 같은 숫자가 있는지 체크
	for (int i = 0; i < 9; i++) {
		if (v[i][x] == select) return false;
		if (v[y][i] == select) return false;
	}

	// 작은 사각형 내에 select 숫자가 있는지 체크
	int ny = y - y % 3;
	int nx = x - x % 3;
	for (int y = ny; y < ny + 3; y++) {
		for (int x = nx; x < nx + 3; x++) {
			if (v[y][x] == select) return false;
		}
	}
	return true;
}

void Sudo(int cnt)
{
	if (cnt == zero.size()) { // 모든 빈칸을 채웠다면 출력하고 종료
		for (int y = 0; y < 9; y++) {
			for (int x = 0; x < 9; x++) {
				cout << v[y][x];
			}
			cout << "\n";
		}
		exit(0); // 정답을 찾으면 프로그램 종료
	}

	// 빈칸에 1부터 9까지의 숫자를 하나씩 시도하며, 유효한 숫자를 찾으면 다음 빈칸으로 넘어간다. 만약 모든 숫자가 유효하지 않다면 이전 빈칸으로 돌아가 다른 숫자를 시도한다.
	int y = zero[cnt].first;
	int x = zero[cnt].second;
	for (int i = 1; i <= 9; i++) {
		if (isPossible(y, x, i)) {
			v[y][x] = i;
			Sudo(cnt + 1); // 다음 빈칸을 채우러 간다
			v[y][x] = 0; // 되돌리기
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string input;
	for (int y = 0; y < 9; y++) {
		cin >> input;
		for (int x = 0; x < 9; x++) {
			v[y][x] = input[x] - '0';
			if (v[y][x] == 0) zero.push_back({ y, x });
		}
	}

	Sudo(0);

	return 0;
}

 

---

 

헷갈린 부분

 

return이 exit(0)을 호출하는 이유는 스도쿠의 해답을 찾았을 때 프로그램을 즉시 종료하기 위함이다.

스도쿠를 풀 때, 백트래킹 방식이 사용되므로 모든 가능성을 탐색해야 한다. 스도쿠의 해답을 찾았다 하더라도, return을 사용하면 해당 함수 호출을 종료하고 이전 함수로 돌아가게 되어, 다른 가능성을 계속 탐색하게 된다. 이는 불필요한 연산을 계속하게 되어 시간초과가 나온다.

그러나 exit(0)을 사용하면 프로그램 전체를 즉시 종료시킨다. 따라서, 스도쿠의 해답을 찾은 후에는 더 이상의 탐색 없이 바로 프로그램이 종료되어 효율성을 높일 수 있다.

여기서 exit(0)의 0은 프로그램이 정상적으로 종료되었음을 운영체제에 알리는 코드다. 다른 숫자를 사용할 경우, 그 숫자에 따른 특정 종료 메시지를 운영체제에 전달하게 된다.

 

 

 

잘못된 코드

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

vector<vector<int>> v(9, vector<int>(9));
vector<pair<int, int>> zero; // 빈 칸의 위치를 저장하는 벡터

bool isPossible(int y, int x, int select)
{
	// (y, x)에 select 숫자를 놓을때 해당 행과 열에 select과 같은 숫자가 있는지 체크
	for (int i = 0; i < 9; i++) {
		if (v[i][x] == select) return false;
		if (v[y][i] == select) return false;
	}

	// 작은 사각형 내에 select 숫자가 있는지 체크
	int ny = y - y % 3;
	int nx = x - x % 3;
	for (int y = ny; y < ny + 3; y++) {
		for (int x = nx; x < nx + 3; x++) {
			if (v[y][x] == select) return false;
		}
	}
	return true;
}

void Sudo(int cnt)
{
	if (cnt == zero.size()) { // 모든 빈칸을 채웠다면 출력하고 종료
		
		return;
		//exit(0); // 정답을 찾으면 프로그램 종료
	}

	// 빈칸에 1부터 9까지의 숫자를 하나씩 시도하며, 유효한 숫자를 찾으면 다음 빈칸으로 넘어간다. 만약 모든 숫자가 유효하지 않다면 이전 빈칸으로 돌아가 다른 숫자를 시도한다.
	int y = zero[cnt].first;
	int x = zero[cnt].second;
	for (int i = 1; i <= 9; i++) {
		if (isPossible(y, x, i)) {
			v[y][x] = i;
			Sudo(cnt + 1); // 다음 빈칸을 채우러 간다
			v[y][x] = 0; // 되돌리기
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string input;
	for (int y = 0; y < 9; y++) {
		cin >> input;
		for (int x = 0; x < 9; x++) {
			v[y][x] = input[x] - '0';
			if (v[y][x] == 0) zero.push_back({ y, x });
		}
	}

	Sudo(0);

	for (int y = 0; y < 9; y++) {
		for (int x = 0; x < 9; x++) {
			cout << v[y][x];
		}
		cout << "\n";
	}

	return 0;
}

 

 

 

return을 사용하고 싶으면 아래와 같이 사용해야 한다.

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

vector<vector<int>> v(9, vector<int>(9));
vector<pair<int, int>> zero; // 빈 칸의 위치를 저장하는 벡터

bool isPossible(int y, int x, int select) 
{
	// (y, x)에 select 숫자를 놓을때 해당 행과 열에 select과 같은 숫자가 있는지 체크
	for (int i = 0; i < 9; i++) {
		if (v[i][x] == select) return false;
		if (v[y][i] == select) return false;
	}

	// 작은 사각형 내에 select 숫자가 있는지 체크
	int ny = y - y % 3;
	int nx = x - x % 3;
	for (int y = ny; y < ny + 3; y++) {
		for (int x = nx; x < nx + 3; x++) {
			if (v[y][x] == select) return false;
		}
	}
	return true;
}

bool Sudo(int cnt)
{
	if (cnt == zero.size()) { // 모든 빈 칸이 채워졌으면 true를 반환하여 재귀 호출을 종료
		
		return true;
	}

	// 빈칸에 1부터 9까지의 숫자를 하나씩 시도하며, 유효한 숫자를 찾으면 다음 빈칸으로 넘어간다. 만약 모든 숫자가 유효하지 않다면 이전 빈칸으로 돌아가 다른 숫자를 시도한다.
	int y = zero[cnt].first;
	int x = zero[cnt].second;
	for (int i = 1; i <= 9; i++) {
		if (isPossible(y, x, i)) {
			v[y][x] = i; // 넣을 수 있으면 넣는다
			if (Sudo(cnt + 1)) return true; // 다음 빈칸을 채우러 간다
			v[y][x] = 0; // 잘못된 선택이었으므로 원래대로 되돌림
		}
	}

	return false; // 현재 빈 칸에 적합한 숫자를 찾지 못했으므로 false 반환
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string input;
	for (int y = 0; y < 9; y++) {
		cin >> input;
		for (int x = 0; x < 9; x++) {
			v[y][x] = input[x] - '0';
			if (v[y][x] == 0) zero.push_back({ y, x });
		}
	}

	if (Sudo(0)) { // 스도쿠를 해결했을 때
		for (int y = 0; y < 9; y++) {
			for (int x = 0; x < 9; x++) {
				cout << v[y][x];
			}
			cout << "\n";
		}
	}
    else { // 스도쿠를 해결하지 못했을 때
    	cout << "잘못된 스도쿠 문제. 풀 수 없는 스도쿠"; 
    };
	
	return 0;
}

 

---