[C++/백준] 2580번: 스도쿠

문제 링크

2580번: 스도쿠

 

풀이

백트래킹 문제

1. 먼저 arr 배열에 입력을 받으면서 0이라면 zero 벡터에 넣어준다.
2. DFS를 시작하는데, zero를 다 채울 때까지(idx가 zero의 사이즈) 반복한다.
3. 0위치에 1~9의 숫자를 모두 넣어봐서 규칙에 맞는지 체크(check)한다.
   1. check함수는 각 세로줄, 가로줄, 네모박스를 체크해서 규칙에 맞으면 true, 아니면 false를 return한다.
4. true라면 해당 위치에 그 숫자를 넣을 수 있는 것이므로 arr[y][x]에 넣고, idx+1를 해서 다시 재귀호출한다.
5. 정답이 여러 개인 경우 하나의 보드만 출력할 수 있도록, 보드가 완성되면 flag = true한다.

 

코드

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

bool flag = false;

bool check(int arr[][9], int curNum, pair<int,int> pos)
{
    int y = pos.first;
    int x = pos.second;
    for (int i = 0; i < 9; i++)
    {
        if (arr[i][x] == curNum) return false; // 세로줄 체크
        if (arr[y][i] == curNum) return false; // 가로줄 체크
    }
    for (int i = 3 * (y / 3); i <= 3 * (y / 3) + 2; i++) // 네모박스 체크
    {
        for (int j = 3 * (x / 3); j <= 3 * (x / 3) + 2; j++)
        {
            if (arr[i][j] == curNum) return false;
        }
    }
    return true;
}

void func(int arr[][9], vector<pair<int,int>> &zero, int idx)
{
    if (flag) return;
    if (idx >= zero.size())
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                cout << arr[i][j] << " ";
            }
            cout << endl;
        }
        flag = true;
        return;
    }
    for (int i = 1; i <= 9; i++)
    {
        if (check(arr, i, zero[idx]))
        {
            int y = zero[idx].first;
            int x = zero[idx].second;
            arr[y][x] = i;
            func(arr, zero, idx+1);
            arr[y][x] = 0;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int arr[9][9];
    vector<pair<int, int>> zero;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 0)
            {
                zero.push_back({ i,j });
            }
        }
    }

    func(arr, zero, 0);

    return 0;
}