#2239번 스도쿠 (C++)

링크 : www.acmicpc.net/problem/2239

2239번: 스도쿠

문제에서 주의할 점은 다음과 같다. 

1. 여러 답이 있다면 사전식으로 앞서는 것을 출력한다고 언급되어있다.

즉, 작은 숫자를 우선적으로 출력하라는 의미인데 

스도쿠는 가로칸 + 세로칸 + 3*3칸에 나오지 않았던 숫자라고 무조건 정답이 되는 것이 아니다. 

상황에따라 사용되지 않은 숫자들이 여러개일 때, 답은 한 개일 수도 있다. 

2. 문자열과 아스키코드의 변환을 주의하자. 48을 +-해주거나 단순히 +'0', -'0'을 해주어 문자형과 숫자형을 변환할 수 있다.

 

문제 풀이는 다음과 같다. 

1. '0'의 값을 갖는 배열의 위치를 vector에 저장해준다. 

2. vector의 값을 순환한다. 가로, 세로, 3*3에 사용되지 않은 숫자를 판별한다. 

    2-(1) 1~9까지 for문을 돌려서 해당 숫자가 사용된 적이 있다면 false를 반환한다.

    2-(2) 사용되지 않았다면 true를 반환한다.

    2-(3) 가로, 세로, 3*3 모두 true로 반환된 값만 사용될 수 있다.

3. 사용되지 않은 숫자가 활용될 수 없었던 케이스라면 다시 값을 초기화하여 백트래킹 한다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
char arr[10][10];
vector<pair<int, int>> ch;

bool row(int y, int x, int n) {
   for(int i=0; i<9; i++){
      if(arr[y][i]==n+48) return false;
   }
   return true;
}

bool col(int y, int x, int n) {
   for(int i=0; i<9; i++){
      if(arr[i][x]==n+48) return false;
   }
   return true;
}

bool three(int y, int x, int n) {
   int t1, t2 = 0;
   t1 = 3 * (y / 3);
   t2 = 3 * (x / 3);
   for (int i = t1; i < t1 + 3; i++) {
      for (int j = t2; j < t2 + 3; j++) {
         if(arr[i][j]==n+48) return false;
      }
   }
   return true;
}

void bt(int cnt) {
   if (cnt>=ch.size()) {
      for (int i = 0; i < 9; i++) {
         for (int j = 0; j < 9; j++) {
            cout << arr[i][j];
         }
         cout << "\n";
      }
      exit(0);
   }
   for(int i=1; i<10; i++){
      if(col(ch[cnt].first, ch[cnt].second, i)&&row(ch[cnt].first, ch[cnt].second, i)&&three(ch[cnt].first, ch[cnt].second, i)){
         arr[ch[cnt].first][ch[cnt].second] = i+48;
         bt(cnt+1);
         arr[ch[cnt].first][ch[cnt].second] = '0';
      }
   }
}

int main(void) {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
         cin >> arr[i][j];
         if (arr[i][j] == '0') ch.push_back(make_pair(i, j));
      }
   }
   bt(0);
   return 0;
}