Boj 2239 c++ 스도쿠

https://www.acmicpc.net/problem/2239

 

아직 채워지지 않은 9 * 9 크기의 스도쿠 보드가 있을 때, 스도쿠 퍼즐을 마저 맞춰야 하는 문제이다.

또한 채운 모습은 오름차순이어야 한다.( 가능한 1 부터 채워나가야 한다는 뜻)

물론 입력은 채울 수 있는 경우만 주어진다.

 

칸은 총 81개이다. 빈칸을 채울 때에는 해당 빈칸의 같은 행, 같은 열, 같은 박스( 3 * 3 ) 안에 같은 수가 있는지 확인해줘야 한다.

만약 이미 수가 있는 경우에는 한 단계 되돌아와야 한다. 사전순으로 채워야 하기에 1부터 채워나가야 한다.

 

불가능한 경우 되돌아와서 다시 시도한다는 아이디어는 백트래킹에 적합하기에 dfs로 구현하면 된다.

 

같은 박스 내에 있는지 확인하는 방법은 해당 인덱스를 i, j 라고 할 때  ( i / 3 ) * 3 에서 ( i / 3 ) * 3 + 3 까지 확인해주면 된다.(j 도 마찬가지)

 

스도쿠 맵 채워나가기는 0, 0 부터 8, 8까지 차례대로 해준다. 인덱스를 숫자로 환산하면 0 ~ 80번 칸이기 때문에 

dfs가 81에 도달하였다는 것은 퍼즐을 모두 완성하였다는 뜻이다. 고로, end flag를 true로 설정해줘야 한다.

 

한칸씩 전진하며 빈칸을 채워나가고, 빈칸을 채울 시에는 1 부터 9 까지 차례대로 채워보는 것 만으로도 정답을 구할 수 있다.

 

 

모두 채우는데에 실패한 경우에는 지도의 상태를 이전으로 되돌려야 한다는 것 또한 잊어서는 안된다.

 

전체 코드

 

#include <iostream>

using namespace std;

char str[10][10];
int mp[10][10];
bool e;

bool ok(int u, int v, int n) {
    for(int i = 0; i < 9; i++) {
        if(mp[u][i] == n)
            return false;
    }

    for(int i = 0; i < 9; i++) {
        if(mp[i][v] == n)
            return false;
    }


    for(int i = 3*(u/3); i < 3*(u/3) + 3; i++) {
        for(int j = 3*(v/3); j < 3*(v/3) + 3; j++){
            if(mp[i][j] == n)
                return false;
        }
    }
    return true;
}

void b_t(int n) {
    if(e)return;
    
    if(n == 81 && !e){
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                cout << mp[i][j];
            }
            cout << "\n";
        }
        e = true;
        return;
    }

    int i = n / 9, j =  n % 9;

    if(mp[i][j] != 0){
        b_t(n+1);
        return;
    }
    for(int k = 1; k <= 9; k++) {
        if(ok(i, j, k)) {

            mp[i][j] = k;
            b_t(n+1);
            mp[i][j] = 0; // 백트래킹
        }
    }
}

int main() {

    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> str[i][j];
            mp[i][j] = int(str[i][j] - '0');
        }
    }
    b_t(0);
}