2580번

2580번 - 스도쿠

처음에는 가로,세로만 확인하고, 3x3 구역은 따로 함수를 만들었더니 시간초과가 발생했다.

그래서 3x3 구역도 배열로 다 만들어서 if문에 의해 체크하는 식으로 만들었더니 AC를 받을 수 있었다.

로직은 

garo[i][j] 는 가로 i번에서 숫자 j 가 있으면 true, 없으면 false

sero[i][j] 는 세로 i번에서 숫자 j 가 있으면 true, 없으면 false

sq[i][j] 는 i번 구역에서 숫자 j 가 있으면 true,없으면 false

이런식으로 배열을 선언하고, 세개 모두 해당하면 빈 숫자를 집어넣는 식으로 재귀함수를 실행했다.

구역은 맨왼쪽 위 3x3 을 0으로, 마지막 오른쪽 맨 아래 3x3 을 9로 생각하고 문제를 풀었다.

<정답 코드>

#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<int>> map(9, vector<int>(9));
 
//출력함수
void print()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}
 
//3x3 확인하기
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]] = true;;
        }
    }
}
void dfs(int c)
{
    //답 구했을 ㅐ
    if (ex)
    {
        return;
    }
        
    //모든 0값 다 바꿨을 때
    if (c == v.size())
    {
        print();
        ex = true;
        return;
    }
 
    int x = v[c].first;                // x좌표
    int y = v[c].second;               // y좌표
    int ar = 3 * (x / 3) + (y / 3);    // x,y좌표의 구역
 
    for (int i = 1; i <= n; i++)
    {
        if (!garo[x][i] && !sero[y][i] && !sq[ar][i] )    //가로,세로,3x3 체크
        {
            garo[x][i] = true;
            sero[y][i] = true;
            sq[ar][i] = true;
            map[x][y] = i;
            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]] = true;
            sero[j][map[i][j]] = true;
            if (map[i][j] == 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);    //3x3 구역 
        }
    }
 
 
    dfs(0);
 
    
    
    return 0;
}