[BOJ] 2239 - 스도쿠

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

BOJ - 스도쿠

문제 유형: 백트래킹, 구현

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 256MB

 

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

 

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

풀이

완전 탐색밖에 답이 없다.

rows[i][num] = i행에 num이 있는지에 대한 여부이다.

cols[j][num] = j열에 num이 있는지에 대한 여부이다.

squares[k][num] = k번째 사각형에 num이 있는지에 대한 여부이다.

 

각 재귀호출마다 가장 앞에 있는(행-열순) 0의 위치를 구해서 소속된 rows, cols, squares에서 공통으로 없는 수들부터 백트래킹을 시작한다.

만약 남은 0이 없다면 행렬을 출력하고 프로그램을 종료한다.

 

 

코드

C++

#include <bits/stdc++.h>
using namespace std;

int board[9][9];
bool rows[9][10];
bool cols[9][10];
bool squares[9][10];

int getSquare(int r, int c) { return (r / 3) * 3 + (c / 3); }

void printMat() {
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      cout << board[i][j];
    }
    cout << "\n";
  }
}

bool findEmpty(int &row, int &col) {
  for (row = 0; row < 9; ++row) {
    for (col = 0; col < 9; ++col) {
      if (board[row][col] == 0)
        return true;
    }
  }
  return false;
}

void solve() {
  int row, col;
  if (!findEmpty(row, col)) {
    printMat();
    exit(0);
  }

  for (int num = 1; num <= 9; ++num) {
    int square = getSquare(row, col);
    if (!rows[row][num] && !cols[col][num] && !squares[square][num]) {
      board[row][col] = num;
      rows[row][num] = cols[col][num] = squares[square][num] = true;

      solve();

      board[row][col] = 0;
      rows[row][num] = cols[col][num] = squares[square][num] = false;
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  string temp;
  for (int i = 0; i < 9; ++i) {
    cin >> temp;
    for (int j = 0; j < 9; ++j) {
      char ch = temp[j];
      if (ch != '0') {
        int num = ch - '0';
        board[i][j] = num;
        rows[i][num] = true;
        cols[j][num] = true;
        squares[getSquare(i, j)][num] = true;
      } else {
        board[i][j] = 0;
      }
    }
  }

  solve();
  return 0;
}