[백준 2239] 스도쿠 (C++)

문제 링크: https://www.acmicpc.net/problem/2239

2239번: 스도쿠

1. 주의할 점

- 사전순으로 가장 빠른 답을 출력한다

- 한번 끝에 도달했으면 더 이상 구하지 않아도 된다

- 0 1 2    의 형태로 블록이 이루어져 있다

  3 4 5

  6 7 8

 

2. 구현

- Finish 변수를 통해 81개의 자리를 모두 채운 적이 있는 경우 더 이상 연산하지 않도록 한다

- Back_track(int num) 함수에 num을 통해 Y값은 num/9, X값은 num%9를 통해 Arr배열의 어떤 Index를 가리키고 있는지 확인한다

- 확인하려는 Index의 값이 0이 아닌 경우, 다음 Index로 넘어간다

- if(arr[y][j]==i || arr[j][x] == i) 를 통해 해당 열과 행에 i 숫자가 있는지 확인한다

- int ny = (y / 3) * 3, int nx = (x / 3) * 3 를 통해 3*3 블록에 겹치는 숫자가 있는지 확인한다

 

#include <iostream>
#include <string>
using namespace std;
bool finish = false;
int arr[9][9];

void back_track(int num) {
	if (finish) return;
	if (num == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << arr[i][j];
			cout << '\n';
		}
		finish = true;
		return;
	}
	int y = num / 9;
	int x = num % 9;
	if (arr[y][x] != 0) back_track(num + 1);
	else {
		for (int i = 1; i < 10; i++) {		//넣으려는 숫자
			bool avail = true;
			for (int j = 0; j < 9; j++) {
				if (arr[y][j]==i || arr[j][x] == i) {
					avail = false;
					break;
				}
			}
			if (!avail) continue;
			int ny = (y / 3) * 3;
			int nx = (x / 3) * 3;
			for (int j = ny; j < ny + 3; j++) {
				for (int k = nx; k < nx + 3; k++) {
					if (arr[j][k] == i) {
						avail = false;
						break;
					}
				}
				if (!avail) break;
			}
			if (avail) {
				arr[y][x] = i;
				back_track(num + 1);
				arr[y][x] = 0;
			}
		}
	}
}

int main() {
	string str;
	for (int i = 0; i < 9; i++) {
		cin >> str;
		for (int j = 0; j < 9; j++) 
			arr[i][j] = str[j] - '0';		
	}
	back_track(0);
	system("pause");
	return 0;
}