백준 2580번: 스도쿠

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

참고한 블로그 : https://yabmoons.tistory.com/88

반례 참고 블로그 : https://cryptosalamander.tistory.com/59

처음에는 9 x 9 보드를 순회하면서 board[i][j] = 0 인 경우에 i행의 모든 숫자, j열의 모든 숫자, i, j가 포함된 3 x 3 사각형의 모든 숫자를 비교해서 1 ~ 9 중 맞는 숫자를 넣도록 하려고 생각을 했다.
그러나 이렇게 할 경우 틀린 해가 되어서 다시 돌아가려고 할 때 어디로 돌아가야하는지에 대한 정보가 없게 됐다. 문제에서 제시한 예제는 답이 나왔는데 다른 반례들에 대해서는 맞게 나오지 않아서 검색을 해서 풀었다.

우선 보드를 2중 for문으로 순회하는 것이 아니라 칸 번호로 순회를 했다. 9 x 9 크기의 보드이므로 전체 칸은 81칸이 될 것이고 칸을 나타내는 num 변수를 dfs 함수의 파라미터로 넘겼다.
num이 주어졌을 때 i = num / 9, j = num % 9라고 인덱스를 구할 수 있으므로 board[i][j]의 값을 찾을 수 있다.

board[i][j] = 0인 경우 빈 칸이므로 1 ~ 9 의 숫자를 순서대로 넣고, 3가지 조건을 확인해서 모두 true인 경우에 다음 칸으로 넘어가서 똑같이 탐색을 진행한다.
아닌 경우는 다른 숫자를 넣어서 비교를 진행하고, 그렇게 모든 칸의 값을 채워 81번째 칸까지 도달한 경우 스도쿠 판을 모두 채운 것이므로 값을 출력하고 종료한다.

<작성한 코드>

#include <iostream>
using namespace std;
int board[9][9];
int n;

void print(){
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++)
            cout << board[i][j] << " ";
        cout << endl;
    }
}

bool check_i(int x){ // 행 숫자 체크
    int numbers[10] = {0, };
    for(int i = 0; i < 9; i++)
        numbers[board[x][i]]++;
        
    for(int i = 1; i <= 9; i++)
        if(numbers[i] >= 2)
            return 0;
    return 1;
}
bool check_j(int y){ // 열 숫자 체크
    int numbers[10] = {0, };
    for(int i = 0; i < 9; i++)
        numbers[board[i][y]]++;
        
    for(int i = 1; i <= 9; i++)
        if(numbers[i] >= 2)
            return 0;
    return 1;
}
bool check_square(int x, int y){ // 사각형 숫자 체크
    int numbers[10] = {0, };
    for(int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
        for(int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)
            numbers[board[i][j]]++;
            
    for(int i = 1; i <= 9; i++)
        if(numbers[i] >= 2)
            return 0;
    return 1;
}

void dfs(int num){
    if(num == 81){ // 81칸을 전부 다 돌았으면 종료
        print();
        exit(0);
    }
    int x = num / 9, y = num % 9;
    if(board[x][y] == 0){
        for(int i = 1; i <= 9; i++){
            board[x][y] = i;
            if(check_i(x) && check_j(y) && check_square(x, y)) // 모두 true이면
                dfs(num + 1); // 다음 숫자 확인
            board[x][y] = 0;
        }
    }
    else
        dfs(num + 1);
}

int main(){
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
            cin >> board[i][j];
    
    dfs(0);
    print();
}

백트래킹을 어느 조건을 걸어서 다시 돌아가는지는 어느 정도 생각이 나는데, 어디로 돌아갈지를 생각하는게 조금 어렵다. 그래도 N-Queen 문제보다는 정답에 가깝게 생각이 나서 한 단계 더 나아갔구나 하는 생각이 들었다. 몇 문제 더 풀어보면 잘 생각할 수 있을지도..?