2239번

2239번 - 스도쿠

2580번 스도쿠랑 똑같은 문제이다.

다만 입력을 2580은 int 타입으로 받았지만, 이 문제는 char 형으로 받아서 변환하면서 문제를 풀었다.

동일한 로직으로 가로, 세로, 구역의 true,false 를 따져가면서 문제를 풀었다.

또한 정답이 여러개일 경우 작은 81자리의 수가 작은 경우로 하라고 했는데, 

재귀함수의 for문이 1부터 시작하기 때문에 문제가 될 것이 없다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
vector<pair<int, int>> v;
int n = 9;
bool ex = false;
bool garo[9][10];
bool sero[9][10];
bool sq[9][10];
vector<vector<char>> map(9, vector<char>(9));
void print()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << map[i][j];
        }
        cout << "\n";
    }
}
void check(int s, int e, int area)
{
    for (int i = s; i < s + 3; i++)
    {
        for (int j = e; j < e + 3; j++)
        {
            sq[area][map[i][j] - '0'] = true;;
        }
    }
}
void dfs(int c)
{
    if (ex)
    {
        return;
    }
 
    if (c == v.size())
    {
        print();
        ex = true;
        return;
    }
 
    int x = v[c].first;
    int y = v[c].second;
    int ar = 3 * (x / 3) + (y / 3);
 
    for (int i = 1; i <= n; i++)
    {
        if (!garo[x][i] && !sero[y][i] && !sq[ar][i])
        {
            garo[x][i] = true;
            sero[y][i] = true;
            sq[ar][i] = true;
            map[x][y] = i + '0';
            dfs(c + 1);
            garo[x][i] = false;
            sero[y][i] = false;
            sq[ar][i] = false;
        }
    }
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    //freopen("input.txt", "r", stdin);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
            garo[i][map[i][j]-'0'] = true;
            sero[j][map[i][j] - '0'] = true;
            if (map[i][j] - '0' == 0)
            {
                v.push_back({ i,j });
            }
        }
    }
 
    int cnt = -1;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cnt++;
            check(i * 3, j * 3, cnt);
        }
    }
 
 
    dfs(0);
 
 
 
    return 0;
}