[C++/백트래킹] 백준 2580 스도쿠

1. 문제

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

2580번: 스도쿠

 

2. 풀이

백트래킹을 이용해 풀었다. 재귀를 이용해 넣을 수 있는 숫자를 계속 넣어가면서 빈칸을 채워가다가 넣을 수 없는 숫자가 온 경우 이전의 빈칸의 숫자를 수정한다. 과정은 다음과 같다.

1. 빈 칸의 좌표를 저장
2. 첫번째 빈칸부터 for문을 이용해 1부터 9까지 숫자를 증가시켜가며 넣을 수 있는 숫자가 있는지 확인한다.
3. 넣을 수 있는 숫자가 있는 경우 그 숫자를 빈 칸에 넣는다.
4. 넣을 수 있는 숫자가 없는 경우 이전 빈칸을 채우는 과정으로 돌아가며 이전 빈칸을 0으로 바꾸고 이전에 넣은 빈칸의 값 다음부터 숫자를 넣어가며 빈칸을 계속 채운다
5. 빈칸을 다채우면 종료한다.

 

3.코드

#include <iostream>
#include <vector>
using namespace std;
 
int sdoku[9][9];
bool isFinished = false;;
vector<pair<int, int>> zeroPoint; // 0인 칸의 좌표 (row, col)
 
// 빈 칸에 숫자가 들어갈 수 있는지 확인
// row, col: 현재 좌표, num: 넣고자 하는 숫자
bool check(int row, int col, int num) {
  // 가로줄, 세로줄 확인
  for (int i = 0; i < 9; i++) {
    if (sdoku[row][i] == num || sdoku[i][col] == num) {
      return false;
    }
  }
  // 좌표가 속한 사각형 확인
  for (int i = row - row % 3; i < row - row % 3 + 3; i++) {
    for (int j = col - col % 3; j < col - col % 3 + 3; j++) {
      if (sdoku[i][j] == num)
        return false;
      }
    }
  }
  return true; // 빈 칸에 num을 넣을 수 있음
}
 
void solve(int zeroIndex) {
  // 모든 0칸 다 채움
  if (zeroIndex == zeroPoint.size()) {
    isFinished = true; // 더이상 빈칸을 바꾸지 않도록
    return;
  }
 
  int nowRow = zeroPoint[zeroIndex].first;
  int nowCol = zeroPoint[zeroIndex].second;
  for (int i = 1; i <= 9; i++) {
    if (check(nowRow, nowCol, i) == true) {
      sdoku[nowRow][nowCol] = i;
      solve(zeroIndex + 1);
      // 스도쿠 칸을 다 채운 후에도 숫자를 바꾸는 것을 막기위해
      if (isFinished == true) return;
      // 한 칸에 어떠한 숫자도 넣을 수 없는 경우 이전 빈칸을 변경하는데
      // 이때 이전 빈칸을 0으로 변경해 빈칸의 값 계속해서 찾는다
      sdoku[nowRow][nowCol] = 0;
    }
  }
}
 
int main() {
  for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
      cin >> sdoku[i][j];
      if (sdoku[i][j] == 0) {
        zeroPoint.push_back({ i, j });
      }
    }
  }
 
  solve(0);
 
  for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
      cout << sdoku[i][j] << " ";
    }
    cout << endl;
    }
}