[BOJ] 백준 2239 스도쿠

문제 링크

www.acmicpc.net/problem/2239

2239번: 스도쿠

 

풀이

생각 없이 풀 수 있는 백트래킹 문제입니다.

 

각 행, 열, 3*3 그룹마다 체크 배열을 만들어 두고 1~9까지의 수가 들어 있는지 비트 마스킹으로 확인합니다.

칸 $(i, j)$는 $(i/3)*3 + j/3$ 번째 그룹$(0-based)$에 포함되어있다는 것만 생각해주시면 됩니다.

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vpii = vector<pii>;

int r[10], c[10], sq[10];
int p[10][10];
const int n = 9;

int sqnum(int x, int y) {
    return (x / 3) * 3 + y / 3;
}

vpii binkan;

bool go(int idx) {
    if (idx == binkan.size()) {
        return true;
    }
    auto[x, y] = binkan[idx];
    int sqidx = sqnum(x, y);
    bool ret = false;
    for (int i = 1; i < n + 1; i++) {
        int bit = 1 << i;
        if ((r[x] & bit) || (c[y] & bit) || (sq[sqidx] & bit)) continue;
        r[x] |= bit;
        c[y] |= bit;
        sq[sqidx] |= bit;
        p[x][y] = i;
        if ((ret |= go(idx + 1))) break;
        p[x][y] = 0;
        r[x] &= ~bit;
        c[y] &= ~bit;
        sq[sqidx] &= ~bit;
    }
    return ret;
}

int main() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &p[i][j]);
            if (p[i][j] == 0) {
                binkan.emplace_back(i, j);
                continue;
            }
            int bit = 1 << p[i][j];
            r[i] |= bit;
            c[j] |= bit;
            sq[sqnum(i, j)] |= bit;
        }
    }
    go(0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d", p[i][j]);
        }
        puts("");
    }
}