BOJ 2580번 스도쿠

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

github : https://github.com/junho0956/Algorithm/blob/master/2580/2580/%EC%86%8C%EC%8A%A4.cpp

 

하나의 실수때문에 2시간이나 날린 문제입니다.. 흑

 

스도쿠를 풀기위한 기본 접근방법은 가로,세로,3*3사각 을 탐색하는것이 아닌

가로,세로,3*3사각 에 맞는 배열을 이용하는 것입니다.

주구장창 탐색만 했다가는 TLE 에 걸립니다.

 

가로, 세로, 9개의 사각형에 대한 사용배열을 미리 만들어두고, dfs 를 통해서 

백트래킹을 하듯이 일단 넣어보고 안되면 리턴하고 이런식으로 코드해주시면 됩니다.

 

가로는 arr 배열의 행 인덱스를 이용해서 row[9][10]; 으로 

세로는 arr 배열의 열 인덱스를 이용해서 col[9][10]; 으로

3*3 사각은 3*3 의 9개 구간을 0,0 0,1 0,2 1,0 1,1 ... 이런식으로 총 3*3 개로 나눈 3차원 visit[3][3][10] 을 사용했습니다

 

실수했던 것은 dfs (int y, int x) 를 받아서 y,x 를 <9 에 해당하는 범위내로 2중포문 돌듯이 구현하였는데

int i = y, ... int j = x 로 하다보니

i 가 다음행으로 증가할때 j 는 0부터 시작해야되는데 x부터 시작하게되는.. 비참한 실수를 하고 말았습니다.

 

이상하게 문제의 예제나 게시판의 반례들은 잘 돌아가길래 결국 처음부터 다시 읽어보니 찾을 수 있었습니다.

좀 더 꼼꼼해야함을 배우고 가는 문제였습니다..

 

#include <iostream>
 
using namespace std;
 
int arr[9][9];
bool row[9][10];
bool col[9][10];
bool visit[3][3][10];
 
bool check(int i, int j, int k) {
    if (row[i][k]) return false;
    if (col[j][k]) return false;
    if (visit[i / 3][j / 3][k]) return false;
 
    return true;
}
 
bool dfs(int y, int x) {
 
    for (int i = y; i < 9; i++) {
        for (int j = x; j < 9; j++) {
            if (!arr[i][j]) {
                bool temp = false;
                for (int k = 1; k <= 9; k++) {
                    if (check(i, j, k)) {
                        temp = true;
                        arr[i][j] = k;
                        row[i][k] = col[j][k] = visit[i / 3][j / 3][k] = true;
                        if (j < 8) temp = dfs(i, j + 1);
                        else temp = dfs(i + 1, 0);
 
                        if (!temp) {
                            arr[i][j] = 0;
                            row[i][k] = col[j][k] = visit[i / 3][j / 3][k] = false;
                            temp = false;
                        }
                    }
                    if (temp) break;
                }
                if (!temp) return false;
            }
        }
        x = 0;
    }
 
    return true;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    for (int i = 0; i < 9; i++) {
        for (int k = 0; k < 9; k++) {
            cin >> arr[i][k];
            if (arr[i][k]) row[i][arr[i][k]] = true, col[k][arr[i][k]] = true, visit[i / 3][k / 3][arr[i][k]] = true;
        }
    }
 
    bool temp = dfs(0, 0);
 
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
 
    return 0;
}