백준 2580번 - 스도쿠 (C++)

문제

해결 방법

3차원배열[3x3으로 나눴을때의 구역][구역 내 세로][구역 내 가로]을 이용하여서 스도쿠 판을 나타내었고, DFS/백트래킹을 통하여 해결하였다.

이 문제에서 사용된 백트래킹은, 구역+가로+세로의 숫자의 종류가 9가지라면(그 칸에 넣을 숫자가 없다면), 재귀를 되돌아가며 기존에 변경한 값을 모두 0으로 되돌려준다.

아쉬웠던 점

3차원배열로 잘 짠거같은데 벡터때문인지 근본적인 무언가 때문인지 약 300ms로, 시간이 예상보다 느리게 나오더라..(빠를줄 알았는데..) 사실 pop만 있고 push는 없는 구조라서 배열을 사용하고 매개변수로 index를 넘겨주면서 충분히 할 수 있었는데 아쉽다. 애지간하면 배열보다 벡터를 사용하는 습관을 들였는데 문제풀이 할 때에는 별로 좋은 습관은 아닌 것 같다. ㅋㅋㅋ

코드

#include <iostream>
#include <vector>
using namespace std;
 
int Map[9][3][3];
bool Clear = false;
 
struct xyz
{
    int x, y, z;
    xyz(int a, int b, int c):x(a), y(b), z(c) {}
};
vector<xyz> ZeroVec;
 
void Sudoku()
{
    if (ZeroVec.empty())
    {
        Clear = true;
        return;
    }
 
    bool NumCheck[10] = {};
    //구역 내 탐색
    int  X= ZeroVec.back().x, Y= ZeroVec.back().y, Z= ZeroVec.back().z;
    for (int _j = 0; _j < 3; ++_j)
        for (int _k = 0; _k < 3; ++_k)
            NumCheck[Map[ZeroVec.back().x][_j][_k]] = true;
 
    //가로
    int SetY = 0, _9SumX = 0, _9SumY = 0, _9CountX = 0, _9CountY = 0;
    if (ZeroVec.back().x > 2 && ZeroVec.back().x < 6)
        SetY = 3; //칸 맨 왼쪽으로 수정.
    if (ZeroVec.back().x > 5 && ZeroVec.back().x < 9)
        SetY = 6;
    
    for (int _i = 0; _i < 3; ++_i)
        for (int _j = SetY; _j < SetY + 3; ++_j)
            NumCheck[Map[_j][ZeroVec.back().y][_i]] = true;
 
    //세로
    SetY = X;
    if (ZeroVec.back().x > 2 && ZeroVec.back().x < 6)
        SetY = ZeroVec.back().x - 3; //칸 맨 위로 수정.
    if (ZeroVec.back().x > 5 && ZeroVec.back().x < 9)
        SetY = ZeroVec.back().x - 6;
    for (int _i = 0; _i < 3; ++_i)
        for (int _j = SetY; _j < 9; _j += 3)
            NumCheck[Map[_j][_i][ZeroVec.back().z]] = true;
   
    //재귀
    for (int l = 1; l < 10; ++l)
        if (!NumCheck[l])
        {
            if (Clear)
                return;
 
            Map[X][Y][Z] = l;
            ZeroVec.pop_back();
            Sudoku();
            if (!Clear)
            {
                Map[X][Y][Z] = 0;
                ZeroVec.emplace_back(X, Y, Z);
            }
        }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            for (int k = 0; k < 3; ++k)
                for (int l = 0; l < 3; ++l)
                    {
                        cin >> Map[i*3 + k][j][l];
                        if (Map[i * 3 + k][j][l] == 0)
                            ZeroVec.emplace_back(i * 3 + k, j, l);
                    }
 
    Sudoku();
 
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                for (int l = 0; l < 3; ++l)
                    cout << Map[i * 3 + k][j][l] << " ";
            }
            cout << "\n";
        }
}

 

잡설 : 다른 사람 풀이를 보면 0ms짜리 풀이도 많더라...