[ BOJ 백준 4574번 - 스도미노쿠 ] 해설 및 코드

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

 

스도미노쿠 예시

 

목적

스도미노쿠의 9x9 그리드에 스도쿠 규칙에 따라,  (1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...)와 같은 도미노 타일 36개를 채워야한다.

 

접근법

1. 0,0~8,8까지의 범위에서, i, j에 해당하는 좌표를 순서대로 방문

2. 해당 좌표에 놓을 수 있는 타일을 상하좌우 네 방향으로 인접한 좌표까지 고려하여 추려낸다.

 

#include<iostream>
#include<cstring>
 
#define init(dst) memset(dst,0,sizeof(dst))
#define useNum(i,j,k) usedNum[0][i][k] = usedNum[1][j][k] = usedNum[2][(i / 3) * 3 + j / 3][k]
 
using namespace std;
 
int b[9][9], di[] = { 1,-1,0,0 }, dj[] = { 0,0,1,-1 };
bool usedTile[10][10], usedNum[3][10][10];
 
bool canUseNum(int i,int j,int k) {
    return !usedNum[0][i][k] && !usedNum[1][j][k] && !usedNum[2][(i / 3) * 3 + j / 3][k];
}
 
bool fill(int i,int j) {
    if (i == 9) return true;
    if (j == 9) return fill(i + 1, 0);
    if (b[i][j] != 0) return fill(i, j + 1);
    
    for (int k = 1; k < 10; ++k) {
        if (!canUseNum(i,j,k))continue;
 
        useNum(i, j, k) = true;
        b[i][j] = k;
        for (int d = 0; d < 4; ++d) {
            int ni = i + di[d], nj = j + dj[d];
            if (ni == -1 || ni == 9 || nj == -1 || nj == 9||b[ni][nj]!=0)continue;
            for (int t = 1; t < 10; ++t)if (!usedTile[k][t] && canUseNum(ni, nj, t)) {
                usedTile[k][t] = usedTile[t][k] = true;
                useNum(ni, nj, t) = true;
                b[ni][nj] = t;
                if (fill(i, j + 1))return true;
                usedTile[k][t] = usedTile[t][k] = false;
                useNum(ni, nj, t) = false;
                b[ni][nj] = 0;
            }
 
        }
        
        useNum(i, j, k) = false;
    }
    b[i][j] = 0;
    return false;
 
 
}
void set(string& s,int val) {
    int y = s[0] - 'A', x = s[1] - '1';
    b[y][x] = val;
    useNum(y, x, val) = true;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int testCase = 1;
    while (true) {
        int n; cin >> n;
        if (n == 0)break;
        
        init(b);init(usedTile);init(usedNum);
        
        for (int i = 1; i < 10; ++i)usedTile[i][i] = true;
        
        string lu, lv, tmp;int y, x, u, v;
        for (int i = 0; i < n; ++i) {
            
            cin >> u >> lu >> v >> lv;
            usedTile[u][v] = usedTile[v][u] = true;
            
            set(lu, u);
            set(lv, v);
        }
 
        for (int i = 1; i < 10; ++i) {
            cin >> lu;
            set(lu, i);
        }
        fill(0,0);
        cout << "Puzzle " << testCase++ << endl;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j)cout << b[i][j];
            cout << endl;
        }
    }
}