[백준 2239] 스도쿠 (C#, C++) - soo:bak

문제 링크

2239번 - 스도쿠

설명

빈칸이 0으로 표시된 9 곱하기 9 스도쿠 보드가 주어질 때, 스도쿠 규칙을 만족하도록 빈칸을 채우는 문제입니다. 해가 여러 개인 경우 사전순으로 가장 앞서는 해를 출력합니다.

접근법

빈칸을 위에서 아래로, 왼쪽에서 오른쪽으로 순회하며 백트래킹으로 채웁니다.

각 칸에서 1부터 9까지 순서대로 숫자를 시도합니다. 해당 숫자가 같은 행, 같은 열, 같은 3 곱하기 3 박스에 이미 존재하면 건너뜁니다. 유효한 숫자를 찾으면 배치하고 다음 칸으로 넘어갑니다.

유효성 검사를 빠르게 하기 위해 행, 열, 박스별로 각 숫자의 사용 여부를 배열에 기록합니다. 숫자를 배치할 때 해당 위치를 참으로 표시하고, 되돌릴 때 거짓으로 복원합니다.

모든 칸을 채우면 해를 찾은 것이므로 출력하고 종료합니다. 각 칸에서 작은 숫자부터 시도하므로 처음 완성되는 해가 사전순으로 가장 앞서는 해입니다.

---

Code

C#

using System;

class Program {
  const int N = 9;
  static int[,] board = new int[N, N];
  static bool[,] row = new bool[N, 10];
  static bool[,] col = new bool[N, 10];
  static bool[,] box = new bool[N, 10];

  static bool Dfs(int idx) {
    if (idx == N * N) return true;
    var r = idx / N;
    var c = idx % N;

    if (board[r, c] != 0) return Dfs(idx + 1);

    var b = (r / 3) * 3 + (c / 3);
    for (var num = 1; num <= 9; num++) {
      if (row[r, num] || col[c, num] || box[b, num]) continue;
      board[r, c] = num;
      row[r, num] = col[c, num] = box[b, num] = true;
      if (Dfs(idx + 1)) return true;
      board[r, c] = 0;
      row[r, num] = col[c, num] = box[b, num] = false;
    }
    return false;
  }

  static void Main() {
    for (var r = 0; r < N; r++) {
      var line = Console.ReadLine()!;
      for (var c = 0; c < N; c++) {
        var v = line[c] - '0';
        board[r, c] = v;
        if (v != 0) {
          row[r, v] = true;
          col[c, v] = true;
          box[(r / 3) * 3 + (c / 3), v] = true;
        }
      }
    }

    Dfs(0);

    for (var r = 0; r < N; r++) {
      for (var c = 0; c < N; c++) Console.Write(board[r, c]);
      Console.WriteLine();
    }
  }
}

C++

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

const int N = 9;
int board[N][N];
bool rowUsed[N][10], colUsed[N][10], boxUsed[N][10];

bool dfs(int idx) {
  if (idx == N * N) return true;
  int r = idx / N, c = idx % N;
  if (board[r][c] != 0) return dfs(idx + 1);

  int b = (r / 3) * 3 + (c / 3);
  for (int num = 1; num <= 9; num++) {
    if (rowUsed[r][num] || colUsed[c][num] || boxUsed[b][num]) continue;
    board[r][c] = num;
    rowUsed[r][num] = colUsed[c][num] = boxUsed[b][num] = true;
    if (dfs(idx + 1)) return true;
    board[r][c] = 0;
    rowUsed[r][num] = colUsed[c][num] = boxUsed[b][num] = false;
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  for (int r = 0; r < N; r++) {
    string s; cin >> s;
    for (int c = 0; c < N; c++) {
      int v = s[c] - '0';
      board[r][c] = v;
      if (v != 0)
        rowUsed[r][v] = colUsed[c][v] = boxUsed[(r/3)*3 + (c/3)][v] = true;
    }
  }

  dfs(0);

  for (int r = 0; r < N; r++) {
    for (int c = 0; c < N; c++) cout << board[r][c];
    cout << "\n";
  }

  return 0;
}