백준 2580번

백준 2580

->사진 출처

www.acmicpc.net/problem/2580

 

[풀이 과정]

 

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

int arr[9][9] = { 0 }; // 스도쿠 배열


void check(int row, int col) {

int real_arr[9] = { 0 };
vector<int> v;

// 가로 세로 체크 
for (int i = 0; i < 9; i++) {

if (arr[row][i])        
real_arr[arr[row][i] - 1] = 1;

if (arr[i][col])       
real_arr[arr[i][col] - 1] = 1;
}

// 첫번째를 기준으로 설정
int sub_row = row / 3; 
int sub_col = col / 3;
  sub_row *= 3; 
  sub_col *= 3;

//  체크하기
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (arr[sub_row][sub_col + j])      
real_arr[arr[sub_row][sub_col + j] - 1] = 1;
}

sub_row++; 
}

// 사용되지 않은 숫자들을 전부 벡터에 넣어준다. 
for (int i = 0; i < 9; i++) {
if (!real_arr[i]) 
v.push_back(i + 1);
}

// 사용되지 않은 숫자가 없을 때
if (!v.size()) return;


//  다음 단계로 넘어간다. 
int next_row = row, next_col = col;

while (true) {
// 다음 col이 9일 때 
if ((++next_col) == 9) {
next_row++;
next_col = 0;

if (next_row == 9) {
arr[row][col] = v[0];
print();
exit(0);
          }
      }
if (next_row == 9) break;
if (arr[next_row][next_col] == 0) break;
}


for (int i = 0; i < v.size(); i++) {
arr[row][col] = v[i];
check(next_row, next_col);
arr[row][col] = 0;
}

}

// 출력 부분

void print() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << arr[i][j];
if (j != 8)
cout << " ";
          }
cout << endl;
      }
}

int main() {

//값 입력하기
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> arr[i][j];
       }
}

// 스도쿠 해결하기 
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (arr[i][j] == 0) {
check(i, j);
              }
      }
}

system("pause");

return 0;
}