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

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

2580번: 스도쿠

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

int arr[9][9];
vector<pii>v;

bool check(int y, int x, int n)
{
    for(int i=0; i<9; i++) //행과 열 확인
    {
        if(arr[y][i]==n || arr[i][x]==n) return false;
    }

    for(int i=0; i<3; i++) //3x3 사각형 확인
    {
        for(int j=0; j<3; j++)
        {
            if(arr[(y/3)*3+i][(x/3)*3+j]==n) return false;
        }
    }

	return true;
}

void func(int idx)
{
    if(idx==v.size()) //전부 탐색했으므로 출력
    {
        for(int i=0; i<9; i++)
        {
            for(int j=0; j<9; j++)
            {
                cout << arr[i][j] << " ";
            }
            cout << "\n";
        }
        exit(0);
    }
    
    auto [y, x] = v[idx]; 

    for(int i=1; i<=9; i++) //1~9의 값 체크
    {
        if(!check(y, x, i)) continue; //i값이 이미 존재한다면 넘김
        arr[y][x]=i; //값 할당
        func(idx+1); //카운팅하고 이후 백트래킹
        arr[y][x]=0;
    }
}

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

    for(int i=0; i<9; i++)
    {
        for(int j=0; j<9; j++)
        {
            cin >> arr[i][j];
            if(arr[i][j]) continue;
            v.push_back({i, j}); //0일 때 좌표저장 (y, x)
        }
    }
    func(0);
    return 0;
}

백준 2239번과 사실상 입력부분만 차이가 있는 문제이다.

2239번을 풀 때는 행, 열, 3x3 사각형 총 3개에 대한 배열을 두고 미리 해당 칸에 값이 있는가 없는가를 판별한 이후에 풀이를 진행했는데, 이번에는 값이 0인 부분에 대해서 좌표를 받고 해당 좌표를 기준으로 탐색하도록 풀어보았다.

 

현재 값이 0일때 좌표를 미리 벡터에 담아둔 뒤 담겨진 좌표들에 대해서 먼저 행, 열, 3x3 사각형에 대해서 i(1~9) 값이 존재하는지 체크를 해준다.

 

배열이 [y][x]이므로 행을 확인할 때는 [y][i]의 값을, 열을 확인할 때는 [i][x]의 값을 확인해준다. (i -> 0~9[범위])

3x3 사각형을 확인할때는 (y/3)*3+i라는 계산을 통해서 총 9칸의 전체 사각형에서 해당 y값이 위치한 3x3 사각형의 첫 번째 좌표를 계산해주고, 이를 기준으로 3칸씩 확인하도록 해준다.

x도 마찬가지로 같은 계산식을 사용해준다.

 

이후에는 현재 배열 arr[y][x]에 i 값을 할당해주고 idx값을 증가시켜서 다음 값을 탐색하도록 해준다.

이와 동시에 백트래킹도 바로 다음줄에 실행시켜서 다른 경우에 대해서도 탐색을 실시한다.

 

0인 경우를 모두 담은 벡터의 사이즈가 idx와 일치하면 넣어야할 0에 대해 모두 탐색이 끝났으므로 출력을 해주고, 이때 주의해야할 것은 스도쿠의 완성 형태가 다양하므로 하나만 출력하기 위해서 exit(0)을 통해 바로 프로세스르 종료시켜준다.