[백준 2239번] 스도쿠 (C++)

문제링크 : https://www.acmicpc.net/problem/2239

2239번: 스도쿠

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[9][9];
bool row[9][9], col[9][9], square[9][9];

void func(int cnt)
{
    int y = cnt/9;
    int x = cnt%9;
    if(cnt==81) //전부 탐색했으므로 출력
    {
        for(int i=0; i<9; i++)
        {
            for(int j=0; j<9; j++)
            {
                cout << arr[i][j];
            }
            cout << "\n";
        }
        exit(0);
    }
    if(arr[y][x]) func(cnt+1); //값이 존재하면 카운팅하고 재귀 호출
    else
    {
        for(int i=1; i<=9; i++) //1~9의 값 체크
        {
            if(row[y][i] || col[x][i] || square[(y/3)*3 + (x/3)][i]) continue; //i값이 이미 존재한다면 넘김
            row[y][i] = 1;
            col[x][i] = 1;
            square[(y/3)*3 + (x/3)][i] = 1;
            arr[y][x]=i; //값 할당
            func(cnt+1); //카운팅하고 이후 백트래킹
            arr[y][x]=0;
            row[y][i] = 0;
            col[x][i] = 0;
            square[(y/3)*3 + (x/3)][i] = 0;
        }
    }
}

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

    for(int i=0; i<9; i++)
    {
        string num;
        cin >> num;
        for(int j=0; j<9; j++)
        {
            arr[i][j] = num[j]-'0';
            if(!arr[i][j]) continue;
            row[i][arr[i][j]] = 1; //y (해당 행에 해당 숫자가 존재 표시)
            col[j][arr[i][j]] = 1; //x (해당 열에 해당 숫자가 존재 표시)
            square[(i/3)*3 + (j/3)][arr[i][j]] = 1; //해당 사각형에 해당 숫자 존재 표시
        }
    }
    func(0);
    return 0;
}

해당 문제에서 3x3 사각형이 9개 있으므로 각 사각형에 대해서도 숫자 존재여부를 체크해주어야 한다.

따라서 확인해야할 사항은 다음과 같이 3가지이다.

전체 9X9 사각형에서 해당 행에 겹치는 값이 있는가?
전체 9x9 사각형에서 해당 열에 겹치는 값이 있는가?
전체 9x9 사각형 중에서 3x3 사각형 안에서 겹치는 값이 있는가?

이를 위해 존재 여부를 확인할 배열 3개(행, 열, 3x3 사각형)를 선언해주고 이를 2차원 배열로 선언해서 해당 행, 열, 사각형에 해당 값이 존재하는지 여부를 체크해준다.

 

이후에 모든 값에 대해서 탐색을 시작한다.

x부터 0 ~ 8의 범위(9개)를 탐색하고 y값이 1칸 증가하는 것을 반복하기에 x=cnt%9, y=cnt/9로 초기화하였다.

이후 해당 좌표 arr[y][x]에 대해서 값이 이미 존재하면 계산할 필요가 없기에 카운팅하고 다음 값 탐색을 시작하고,

값이 0이라면 새로운 값을 대입해주어야 하기 때문에 반복문으로 1~9까지 돌리고 해당 값들이 들어갈 수 있는지 없는지를 판별해준다.

 

1~9까지의 값에 대해 각각 현재 행, 열, 3x3 사각형에 대해서 해당 값이 존재하는지 여부를 체크하고 있다면 넘기고 없다면 해당 값에 할당을 해주고 행, 열, 3x3 사각형에 대해 방문 처리를 해준다.

이렇게 할당이 끝났으면 마찬가지로 카운팅을 하고, 다른 경우도 존재할 수 있으므로 백트래킹을 진행해준다.

 

이를 모든 값을 탐색해야 하기에 9x9의 값인 cnt가 81이 될 때까지 반복하여 탐색을 돌려주고 출력해준다.

출력할때 주의해야 할 것은 맨 처음 출력하고 exit(0)을 통해서 프로세스를 종료시켜주어야 한다는 점이다.

스도쿠가 다른 형태로도 완성될 수 있으므로 첫 번째 완성이후로도 출력이 될 수 있어서 exit(0)이 없다면 출력초과가 발생한다.