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

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

2580번: 스도쿠

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

해당 문제와 완전히 같은 방식으로 푸는 문제였습니다.

https://junseok.tistory.com/316

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

 

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

#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;
}

 

 

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