백준 2239 스도쿠 (c++) : 피너클

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

2239번: 스도쿠

구현문제다.

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

	for (int i = 0; i < 9; i++) cin >> sudoku[i];

	solve(0, 0);
}

string으로 입력받는다.

void solve(int y, int x) {
	if (sudoku[y][x] == '0') {

solve함수다.

solve함수는 현재 위치를 전달받는다. 만약 현재 위치 값이 0이라면

		for (int i = 1; i <= 9; i++) {
			sudoku[y][x] = '0' + i;
			if (can(y, x)) {
				if (y == 8 && x == 8) {
					p();
				}
				if (x == 8)  solve(y + 1, 0);
				else  solve(y, x + 1);
			}
			sudoku[y][x] = '0';
		}
	}

현재 위치에 1 ~ 9까지의 숫자를 전부 집어넣는다.

만약 can(y, x)가 true로 반환된다면 다음으로 넘어가거나 출력해야한다.

y == 8이고 x == 8이면 끝까지 도착했다는 뜻이니 p()함수를 실행한다. p()는 직접 구현한 함수다.

x == 8이라면 아래칸으로 이동해야한다. y+1, 0을 solve에 넣는다.

x != 8이라면 옆칸으로 이동해야하낟. y, x + 1을 solve에 넣는다.

그후 sudoku칸을 원래데로 되돌려놓는다.

	else {
		if (y == 8 && x == 8) {
			p();
		}
		if (x == 8)  solve(y + 1, 0);
		else  solve(y, x + 1);
	}
}

sudoku[y][x]가 0이 아니라면 다음으로 넘어가야한다. 위에서 나온것처럼 다음으로 넘어간다.

void p() {
	for (int i = 0; i < 9; i++) cout << sudoku[i] << endl;
	exit(0);
}

p()함수다. sudoku를 전부 출력한뒤 exit(0)을 통해 강제종료 시킨다.

exit(0)을 이용하면 main이 아닌 다른 함수 실행중에도 프로그램을 종료시킬 수 있다.

can(y, x)는 너무 노가다 구현이어서 따로 설명은 안한다. 좌우, 위아래를 확인하고 현재 속한 정사각형을 확인한다.

#include <iostream>
#include <string>

using namespace std;

string sudoku[9];

bool can(int y, int x) {
	for (int i = 0; i < 9; i++) {
		if (sudoku[y][x] == sudoku[y][i]) {
			if (i != x) return false;
		}
	}
	for (int i = 0; i < 9; i++) {
		if (sudoku[y][x] == sudoku[i][x]) {
			if (i != y) return false;
		}
	}
	if (y < 3 && x < 3) {
		for (int i = 0; i < 3; i++) 
			for (int j = 0; j < 3; j++) 
				if (sudoku[i][j] == sudoku[y][x]) 
					if (i != y || j != x) return false;
	}
	else if (y < 3 && x < 6) {
		for (int i = 0; i < 3; i++)
			for (int j = 3; j < 6; j++)
				if (sudoku[i][j] == sudoku[y][x])
					if (i != y || j != x) return false;
	}
	else if (y < 3 && x < 9) {
		for (int i = 0; i < 3; i++)
			for (int j = 9; j < 9; j++)
				if (sudoku[i][j] == sudoku[y][x])
					if (i != y || j != x) return false;
	}
	else if (y < 6 && x < 3) {
		for (int i = 3; i < 6; i++)
			for (int j = 0; j < 3; j++)
				if (sudoku[i][j] == sudoku[y][x])
					if (i != y || j != x) return false;
	}
	else if (y < 6 && x < 6) {
		for (int i = 3; i < 6; i++)
			for (int j = 3; j < 6; j++)
				if (sudoku[i][j] == sudoku[y][x])
					if (i != y || j != x) return false;
	}
	else if (y < 6 && x < 9) {
		for (int i = 3; i < 6; i++)
			for (int j = 9; j < 9; j++)
				if (sudoku[i][j] == sudoku[y][x])
					if (i != y || j != x) return false;
	}
	else if (y < 9 && x < 3) {
		for (int i = 6; i < 9; i++)
			for (int j = 0; j < 3; j++)
				if (sudoku[i][j] == sudoku[y][x])
					if (i != y || j != x) return false;
	}
	else if (y < 9 && x < 6) {
		for (int i = 6; i < 9; i++)
			for (int j = 3; j < 6; j++)
				if (sudoku[i][j] == sudoku[y][x])
					if (i != y || j != x) return false;
	}
	else if (y < 9 && x < 9) {
		for (int i = 6; i < 9; i++)
			for (int j = 9; j < 9; j++)
				if (sudoku[i][j] == sudoku[y][x])
					if (i != y || j != x) return false;
	}
	return true;
}

void p() {
	for (int i = 0; i < 9; i++) cout << sudoku[i] << endl;
	exit(0);
}

void solve(int y, int x) {
	if (sudoku[y][x] == '0') {
		for (int i = 1; i <= 9; i++) {
			sudoku[y][x] = '0' + i;
			if (can(y, x)) {
				if (y == 8 && x == 8) {
					p();
				}
				if (x == 8)  solve(y + 1, 0);
				else  solve(y, x + 1);
			}
			sudoku[y][x] = '0';
		}
	}
	else {
		if (y == 8 && x == 8) {
			p();
		}
		if (x == 8)  solve(y + 1, 0);
		else  solve(y, x + 1);
	}
}

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

	for (int i = 0; i < 9; i++) cin >> sudoku[i];

	solve(0, 0);
}

전체코드다.