[Baekjoon/C++] 2239번 - 스도쿠

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

 

입력

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

 

출력

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

 

---

풀이

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

int sudoku[9][9];
vector<pair<int, int>> zero;

bool canFill(int y, int x, int num);
void fillZero(int idx);

bool canFill(int y, int x, int num) {
    for (int i = 0; i < 9; i++) {
        if (sudoku[y][i] == num && i != x) return false;
        if (sudoku[i][x] == num && i != y) return false;

        int ny = y / 3 * 3 + i / 3;
        int nx = x / 3 * 3 + i % 3;

        if (sudoku[ny][nx] == num && nx != x && ny != y) return false;
    }

    return true;
}

void fillZero(int idx) {
    if (idx == zero.size()) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) cout << sudoku[i][j];
            cout << '\n';
        }

        exit(0);
    }

    int y = zero[idx].first;
    int x = zero[idx].second;

    for (int i = 1; i <= 9; i++) {
        if (canFill(y, x, i)) {
            sudoku[y][x] = i;
            fillZero(idx + 1);
            sudoku[y][x] = 0;
        }
    }
}

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

    for (int i = 0; i < 9; i++) {
        string s;
        cin >> s;

        for (int j = 0; j < 9; j++) {
            sudoku[i][j] = (s[j] - '0');

            if (sudoku[i][j] == 0) zero.push_back({ i, j });
        }
    }

    fillZero(0);

    return 0;
}

 

    for (int i = 0; i < 9; i++) {
        string s;
        cin >> s;

        for (int j = 0; j < 9; j++) {
            sudoku[i][j] = (s[j] - '0');

            if (sudoku[i][j] == 0) zero.push_back({ i, j });
        }
    }

 입력 받은 숫자를 배열에 넣는 부분의 코드이다. 해당하는 칸의 값이 0이라면 zero에 넣는다.

 

bool canFill(int y, int x, int num) {
    for (int i = 0; i < 9; i++) {
        if (sudoku[y][i] == num && i != x) return false;
        if (sudoku[i][x] == num && i != y) return false;

        int ny = y / 3 * 3 + i / 3;
        int nx = x / 3 * 3 + i % 3;

        if (sudoku[ny][nx] == num && nx != x && ny != y) return false;
    }

    return true;
}

 해당 칸에 num을 넣을 수 있는지 확인하는 함수이다. 가로, 세로, 3*3 칸에 넣으려는 숫자 num이 존재하는지 확인한다.

 

void fillZero(int idx) {
    if (idx == zero.size()) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) cout << sudoku[i][j];
            cout << '\n';
        }

        exit(0);
    }

    int y = zero[idx].first;
    int x = zero[idx].second;

    for (int i = 1; i <= 9; i++) {
        if (canFill(y, x, i)) {
            sudoku[y][x] = i;
            fillZero(idx + 1);
            sudoku[y][x] = 0;
        }
    }
}

 백트래킹으로 스도쿠의 칸을 채우는 함수이다. idx가 zero의 크기와 같아진다면 모든 칸에 숫자가 채워진 것이므로 답을 출력하고 프로그램을 끝내도록 했다.