[백준 2580번] 스도쿠

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

2580번: 스도쿠

풀이) 

백트래킹으로 현재 위치(0)에서 가능한 경우의 수를 구하고 가능하면 해당 숫자를 넣고 dfs를 돌리고 다시 나왔을 때는 다른 수를 넣어야하므로 0으로 다시 처리를 해두었다. 만들 수 있는 경우의 수가 여럿있어서(?) 기재조건에 exit(0) - 정상종료를 시키지 않았더니 틀렸다고 채점되었다(..? 시간초과가 아닌..) 여튼.. 그래서 넣어두었다.

#include <iostream>
#include <vector>
using namespace std;

int map[9][9];
vector<pair<int, int> > v;

int rowCheck(int x, int y, int n)
{
    for (int i = 0; i < 9; i++)
        if (n == map[x][i])
            return (0);
    return (1);
}

int columnCheck(int x, int y, int n)
{
    for (int i = 0; i < 9; i++)
        if (n == map[i][y])
            return (0);
    return (1);
}

int SquareCheck(int x, int y, int n)
{
    int sx = (x / 3) * 3;
    int sy = (y / 3) * 3;
    for (int i = sx; i < sx + 3; i++)
        for (int j = sy; j < sy + 3; j++)
            if (n == map[i][j])
                return (0);
    return (1);
}

int dfs(int x, int y, int n)
{
    if (n == v.size() + 1)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
                cout << map[i][j] << " ";
            cout << "\n";
        }
        exit(0);
    }

    for (int i = 1; i <= 9; i++)
    {
        if (rowCheck(x, y, i) && columnCheck(x, y, i) && SquareCheck(x, y, i))
        {
            map[x][y] = i;
            dfs(v[n].first, v[n].second, n + 1);
            map[x][y] = 0;
        }
    }
    return (0);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> map[i][j];
            if(map[i][j] == 0)
                v.push_back(make_pair(i,j));
        }
    }
    dfs(v[0].first, v[0].second, 1);
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!