백준 2580 / 스도쿠

백트래킹로도 풀 수 있지만 충분히 DFS로도 가능한 문제.

처음에 접근을 잘못해서 굉장히 헤멨다.

garo[i][j]는 i 번쨰 가로에 j라는 수가 들어갔는지를 나타내는... 식으로 sero와 sq를 선언했다.

그중에서도 3X3 구역을 정하는 3*(x/3) + (y/3) 같은 수식을 만들어내는 머리가 필요한 문제다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int n = 9;
int map[9][9];
vector<pair<int, int>>v;
bool garo[9][10];
bool sero[9][10];
bool sq[9][10];
 
bool out = false;
 
void dfs(int idx) {
 
    if (out) {
        return;
    }
 
    if (idx == v.size()) {
 
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << map[i][j] << " ";
            }
            cout << endl;
        }
        out = true;
        return;
    }
 
    int x = v[idx].first;
    int y = v[idx].second;
    int sqnum = 3 * (x / 3) + (y / 3);
 
    for (int i = 1; i <= 9; i++) {
 
        if (garo[x][i] == false && sero[y][i] == false && sq[sqnum][i] == false) {
            garo[x][i] = true;
            sero[y][i] = true;
            sq[sqnum][i] = true;
            map[x][y] = i;
            dfs(idx + 1);
 
            garo[x][i] = false;
            sero[y][i] = false;
            sq[sqnum][i] = false;
        }
    }
}
 
void sqcheck(int il, int jl, int sqnum) {
    for (int i = il; i < il + 3; i++) {
        for (int j = jl; j < jl + 3; j++) {
 
            sq[sqnum][map[i][j]] = true;
        }
 
    }
}
 
int main() {
    //freopen("Text.txt", "r", stdin);
    int cnt = 0;
 
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> map[i][j];
            garo[i][map[i][j]] = true;
            sero[j][map[i][j]] = true;
            if (map[i][j] == 0)
                v.push_back(make_pair(i, j));
        }
    }
 
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
 
            sqcheck(i * 3, j * 3, cnt);
            cnt++;
        }
    }
 
    dfs(0);
 
    return 0;
}