[BOJ] 2580 - 스도쿠

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

2580번: 스도쿠

#include <iostream>
#include <vector>
using namespace std;

int cnt = 0;
bool flag = false;
int board[9][9] = {0, };
vector<pair<int, int>> blank;

bool check(int x, int y){
    int square_x = x % 3;
    int square_y = y % 3;

    for(int i = 0; i < 9; i++){
        if(board[x][i] == board[x][y] && i != y)
            return false;
        if(board[i][y] == board[x][y] && i != x)
            return false;
    }

    for(int i = x - square_x; i < x - square_x + 3; i++){
        for(int j = y - square_y; j < y - square_y + 3; j++){
            if(i == x && j == y)
                continue;
                
            if(board[i][j] == board[x][y])
                return false;
        }
    }
    return true;
}

void func(int n){
    if(n == cnt){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                cout << board[i][j] << ' ';
            }
            cout << '\n';
        }
        flag = true;
        return;
    }
    int x = blank[n].first;
    int y = blank[n].second;

    for(int i = 1; i <= 9; i++){
        board[x][y] = i;
        if(check(x, y)){
            func(n+1);
        }
        if(flag)
            return;
    }
    board[x][y] = 0;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            cin >> board[i][j];
            if(board[i][j] == 0){
                blank.push_back(make_pair(i, j));
                cnt++;
            }
        }
    }
    func(0);
}

백트래킹을 대표하는 문제인 9663번 N-Queen 문제와 유사한 듯 더 까다로웠던 백트래킹 문제이다.

빈 칸인 좌표를 따로 vector에 추가해두고 해당 좌표들에 대해서 1 ~ 9의 값들을 대입하며 check 함수를 통해 유망성을 검사한다.

bool check(int x, int y){
    int square_x = x % 3;
    int square_y = y % 3;

    for(int i = 0; i < 9; i++){
        if(board[x][i] == board[x][y] && i != y)
            return false;
        if(board[i][y] == board[x][y] && i != x)
            return false;
    }

    for(int i = x - square_x; i < x - square_x + 3; i++){
        for(int j = y - square_y; j < y - square_y + 3; j++){
            if(i == x && j == y)
                continue;
                
            if(board[i][j] == board[x][y])
                return false;
        }
    }
    return true;
}

check 함수에서는 같은 행 / 같은 열 / 같은 3x3 칸에 중복되는 값이 있는지를 확인한다.

check 함수가 true인 경우 다음 빈 칸 좌표에 대해서 func 함수를 호출한다.

 

void func(int n){
    if(n == cnt){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                cout << board[i][j] << ' ';
            }
            cout << '\n';
        }
        flag = true;
        return;
    }
    int x = blank[n].first;
    int y = blank[n].second;

    for(int i = 1; i <= 9; i++){
        board[x][y] = i;
        if(check(x, y)){
            func(n+1);
        }
        if(flag)
            return;
    }
    board[x][y] = 0;
    return;
}

만약 func 함수에서 n이 빈 칸의 개수인 cnt와 같아지면 모든 빈 칸에 대해 숫자를 채운 것이므로 스도쿠 판을 출력하게 된다. 여기서 출력 이후 판이 완성되었다는 의미로 flag를 true로 바꾸어주어야 하는데 그렇지 않으면 또 새로운 숫자에 대해서 함수를 진행하게 된다. 스도쿠의 모든 경우가 아닌 가장 먼저 판이 채워지는 경우를 구하면 되므로 flag가 true이면 바로 return해준다.

 

board[x][y] == 0이라는 문장까지 온 경우는 해당 칸에 대해서 1 ~9를 모두 대입했지만 판을 완성할 수 없는 경우이다.

이 경우 다시 빈 칸의 상태로 돌려 놓은 뒤 return을 해주어야 한다.

---

느낀 점

빈 칸의 좌표를 따로 저장해두는 스킬은 앞으로 유용하게 쓰일 것 같다.

큰 틀은 감을 잡고 진행했지만 사소한 부분에서 놓친 부분이 많은 문제였다.

먼저 판이 완성되고 출력을 한 이후에 for문을 그만돌게 해주어야 하는데 그렇지 해주지 못했다.

또한 백트래킹 할 때 칸은 원상 복구해주는 부분도 생각하지 못했다.

재귀적인 문제를 풀 때 항상 어려움을 느끼는데 백트래킹 문제를 많이 연습해야겠다.