백준 2239 -스도쿠(C++)

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

2239번: 스도쿠

백트래킹을 이용하는 문제입니다.

기본 스도쿠가 주어졌을 때, 가능한 스도쿠 중 조건에 만족하는 것을 구하는 문제입니다.

 

스도쿠를 채울 수 있는 경우는 3가지입니다.

1. 자신이 속한 3*3 사각형 내에 겹치는 수가 없다.

2. 자신이 속한 행에 겹치는 수가 없다.

3. 자신이 속한 열에 겹치는 수가 없다.

이 3가지 조건을 만족해야 스도쿠를 채울 수 있습니다.

저는 각각 square, row, col 배열을 통해 이를 판별했습니다.

 

먼저 스도쿠를 3*3 사각형 9개로 나눠야합니다. 나눈 사각형을 (0, 0) ~ (2, 2)로 구분했습니다. 오른쪽 아래가 (2, 2)입니다.

행렬은 간단합니다. 자신이 속한 행렬을 확인해주면 됩니다.

 

스도쿠에 들어갈 수 있는 수는 1~9입니다, 따라서 (X, Y)좌표에 1~9를 전부 넣어봅니다. -> 백트래킹으로 만들어줍니다.

 

스도쿠를 만들 수 있는 첫번째 경우가 81번째 수가 가장 작은 경우입니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>
#define PP pair<P, int>
#define F first
#define S second
#define LL long long
#define INF 9876543210
using namespace std;

int map[10][10];
int row[10][10]; //행의 X번째에서 Y값을 사용?
int col[10][10]; //열의 X번째에서 Y값을 사용?
int square[4][4][10]; //(X,Y) 사각형에서 Z값 사용?
int num = 0;

bool fill_square(int cnt){
    num += 1;
    if(num >= 10000000) return true;
    if(cnt == 81){
        for(int i = 0; i < 9; i++){
           for(int j = 0; j < 9; j++){
               cout << map[i][j];
            }
            cout << "\n";
        }
        return true;
    }
    int x = cnt/9;
    int y = cnt%9;
    if(map[x][y] != 0) return fill_square(cnt+1);
    else{
       for(int k = 1; k <= 9; k++){
            if(square[x/3][y/3][k] != 0) continue;
            if(row[x][k] != 0) continue;
            if(col[y][k] != 0) continue;
            square[x/3][y/3][k] = 1;
            row[x][k] = 1; 
            col[y][k] = 1;
            map[x][y] = k;
            if(fill_square(cnt+1)) return true;
            square[x/3][y/3][k] = 0;
            row[x][k] = 0;
            col[y][k] = 0;
            map[x][y] = 0;
        }
    }
    return false;
}

void solve(){
    fill_square(0);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	for(int i = 0; i < 9; i++){
	    for(int j = 0; j < 9; j++){
	        scanf("%01d", &map[i][j]);
	        if(map[i][j] != 0){
	            row[i][map[i][j]] = 1;
	            col[j][map[i][j]] = 1;
	            square[i/3][j/3][map[i][j]] = 1;
	        }
	    }
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요