[백준] 2508번 스도쿠 C++

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

C++

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

// 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한번씩만
// 3x3 정사각형 안에서도 1부터 9까지

int arr[10][10];
int check = 0;
vector<pair<int,int>> v;
bool finish = false;

bool search(int row, int col) {
    // 전체 가로와 세로 판단해야하고 9개 칸 정사각형 확인해야함

    // 자기 자신과의 비교는 막아야 한다!! 계속 출력이 안나왔던 이유
    for(int i = 0; i < 9; i++) {
        if (arr[i][col] == arr[row][col] && i != row) {
            return false;
        }
    }
    for(int j = 0; j < 9; j++){
        if(arr[row][j] == arr[row][col] && j != col) {
            return false;
        }
    }
    int squRow = row / 3;
    int squCol = col / 3;
    for(int i = 3 * squRow; i < 3 * squRow + 3; i++) {
        for(int j = 3 * squCol; j < 3 * squCol + 3; j++) {
            if(arr[i][j] == arr[row][col] && (i != row || j != col)) {
                return false;
            }
        }
    }
    return true;
}

void find(int num) {
    if(num == check) { // 0으로 적힌 곳 모두 채웠다
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                cout << arr[i][j] << " ";
            }
            cout << "\n";
        }
        finish = true;
        return;
    }
    int x = v[num].first;
    int y = v[num].second;

    for(int i = 1; i < 10; i++) {
        arr[x][y] = i;
        if(search(x,y)) {
            find(num + 1);
        }
        if(finish) {
            return;
        }
    }
    arr[x][y] = 0;
}

int main() {
    // 빈칸 0으로 주어진다.
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 여기서 0이 입력되면 우리가 확인해야되는 곳이다.
    // 그럼 이것도 백트래킹 dfs를 써야되는건데...
    // 그렇다면 0인곳만 판단하면 되는거잖아?

    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> arr[i][j];
            if(arr[i][j] == 0) {
                v.push_back({i,j});
                check++;
            }
        }
    }
    find(0);
}

문제풀이

• 전체 스도쿠판의 가로 세로줄에 있는 각 숫자가 겹치면 안되고 9칸의 정사각형 내에서도 겹치면 안된다. 그리고 우리가 확인되어야 하는 곳은 0으로 입력된다. 그렇다면 0으로 입력된 곳에만 1~9의 숫자를 넣어보면 된다. 그리고 어떤 숫자가 가능한지 확인하기 위해서 가로세로줄과 정사각형 안에 그 숫자가 없는지 확인한다. 그래서 먼저 arr에 숫자 입력받을 때 0으로 된 곳을 따로 v에 저장했다. search 함수는 숫자의 당위성을 파악하는 함수이다. 가로 세로줄에 같은 숫자가 있는지 확인할 때 자기 자신은 제외해야된다는 것을 잊으면 안된다! 그리고 정사각형 안에서 같은 숫자가 있는지 파악하기 위해 새로운 변수 squRow, squCol을 사용했다. 모든 조건을 만족한다면 true를 반환했다. 1~9의 숫자를 넣는 함수는 find로서 백트래킹 DFS를 이용해서 구현했다. 0으로 입력된 곳의 좌표를 x,y로 나타내고 search(x,y)를 했을 때 true를 반환하면 적절한 값이 들어간 것이고 아닌 경우에는 틀렸기 때문에 다시 0으로 초기화한다. 0의 개수만큼 find함수를 돌리고, 모든 곳에 적절한 숫자가 들어가면 최종 스도쿠를 출력한다.

Comment

• 이 문제는 2일정도 고민하고 풀었던 복잡한 문제였다. 가로와 세로에 같은 숫자가 있는지 판단할 때 자기 자신을 제외하지 않아서 긴 시간동안 아무것도 출력되지 않았다. 그리고 정사각형 내에 숫자를 비교할 때 어떤식으로 해야할지 감이 잡히지 않았다. 백트래킹 문제를 연속으로 계속 풀고있지만 그럼에도 참 어려운 것 같다...