2580번: 스도쿠(백준 C++)

2580번: 스도쿠 링크

코드

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

int arr[9][9];
vector <pair<int, int>> list;

void init(){
   for(int i=0; i<9; i++){
      for(int j=0; j<9; j++){
         cin >> arr[i][j];
         if(arr[i][j] == 0) list.push_back(make_pair(i, j));
      }
   }
}
int full(){
  int cnt = 0;
  for(int i=0; i<9; i++){
    for(int j=0; j<9; j++){
      if(arr[i][j] == 0) cnt++;
    }
  }
  return cnt;
}
void p(){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout << arr[i][j] << " ";
        }
        cout <<  "\n";
    }
}
bool check(int i, int j, int num){
   //가로
   for(int w=0; w<9; w++){
      if(arr[i][w] == num) return false;
   }
   //세로
   for(int h=0; h<9; h++){
      if(arr[h][j] == num) return false;
   }
   //33정사각형
   int temp_x = (i/3) * 3;
   int temp_y = (j/3) * 3;
   for(int x = temp_x; x < temp_x+ 3; x++){
      for(int y = temp_y; y < temp_y + 3; y++){
         if(arr[x][y] == num) return false;
      }
   }
   return true;

}

void solve(int index){
  int cnt = full();
  if(cnt == 0) {
    p();
    exit(0);
  }
  else{
    for(int i=1; i<10; i++){
      if(check(list[index].first, list[index].second, i)){
        arr[list[index].first][list[index].second] = i;
        solve(index+1);
        arr[list[index].first][list[index].second] = 0;
      }
    }
  }
}

int main(){
   init();
   solve(0);
}

풀이 및 사견

아직 내 실력이 많이 부족하다는 것을 느끼고 있다.
골드 문제에 들어오면서부터 부쩍 막히는 시간이 길어졌다.

그래도 이번 문제는 어제 N-Queen에서 하도 고난했더니 그렇게 힘들진 않았다.

9X9 사이즈 스도쿠 생성

int arr[9][9];

크게 설명할 부분이 없다. 스도쿠를 채우려면 스도쿠를 만들어야 하는 법이다.

(중요) 공백 부분 모아서 따로 정리하기.

스도쿠에서 우리가 채워야 하는 공백 부분이 있다. 이것들을 Vector 와 Pair를 사용하여 좌표를 저장해준다.
사실 이 부분을 따로 정리하지 않아도 문제해결은 가능할 것이나 아마 시간측면에서 상당히 손해를 보게 될 것이다.

vector <pair<int, int>> list;

void init(){
   for(int i=0; i<9; i++){
      for(int j=0; j<9; j++){
         cin >> arr[i][j];
         if(arr[i][j] == 0) list.push_back(make_pair(i, j)); // 공백이면 그 좌표를 Vector 저장
      }
   }
}

해결

이제 해결은 간단하다. 따로 모아놓은 Vector 내의 좌표에 차례대로 수를 넣어보며 백트래킹을 하면 된다.

void solve(int index){
  int cnt = full();
  if(cnt == 0) {
    p();
    exit(0);
  }
  else{
    for(int i=1; i<10; i++){
      if(check(list[index].first, list[index].second, i)){
        arr[list[index].first][list[index].second] = i;
        solve(index+1);
        arr[list[index].first][list[index].second] = 0;
      }
    }
  }
}

반복문 i는 공백에 들어갈 숫자이다.
i가 공백에 들어갈 수 있는지 없는지는 Check 함수로 확인하는데

bool check(int i, int j, int num){
   //가로
   for(int w=0; w<9; w++){
      if(arr[i][w] == num) return false;
   }
   //세로
   for(int h=0; h<9; h++){
      if(arr[h][j] == num) return false;
   }
   //33정사각형
   int temp_x = (i/3) * 3;
   int temp_y = (j/3) * 3;
   for(int x = temp_x; x < temp_x+ 3; x++){
      for(int y = temp_y; y < temp_y + 3; y++){
         if(arr[x][y] == num) return false;
      }
   }
   return true;

}

코드 읽기 편하게 하려고 이렇게 가로, 세로, 33 정사각형부분으로 나누었다.
이거를 반복문 하나돌리면서 다 확인할 수도 있긴하다.

어쨌든 들어오는 좌표 (i, j)에 대해 num이 들어가도 되는지 확인하는 것이며

가로 즉, 좌표 i를 고정하고 다른 부분을 움직이며 확인
세로는 좌표 j를 고정하고 다른 부분을 움직이며 확인한다.

그리고 3 X 3 작은 정사각형을 만족하는지는

이 그림을 보면서 생각해보자.

여기에 규칙이 있다.

한 블럭의 좌표를 통해서, 그 블럭이 어떤 3X3 사각형에 속해있는지 알 수 있다는 것이다.

위에 좌표가 들어간 부분을 살펴보자.

만약 내가 arr[4][8] 이 어떤 사각형에 속해있는지 찾아야 한다고 가정할때

4는 35 사이에 속하고, 8이 68 사이에 속하므로

arr[3:5][6:8] 인 3X3에 속함을 알 수 있다.

그리고 이를 수식화 한다면,

arr[i][j] 좌표인 경우

arr [{(i / 3) * 3} ~ {(i / 3) * 3 + 3}][{(j / 3) * 3} ~ {(j / 3) * 3 + 3}]
의 사각형에 속함을 알 수 있다.

이러한 조건을 충족하는지 확인하며 백트래킹을 진행해주면 스도쿠를 완성할 수 있다.

재귀함수의 종료 같은 경우에는

스도쿠 내에 공백이 없을경우 -> 프로그램 자체를 종료해버리는 exit(0)를 사용해주자.