[C++] BOJ(백준) 2239 스도쿠

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

2239번: 스도쿠

 

백트래킹 문제다.

스도쿠를 완성시키면 되는 문제인데 이와 유사한 문제로 2580 스도쿠 문제가 있다.

두 문제의 차이점은 입력에서 공백의 유무가 전부다.

2580 문제를 전에 푼 적이 있어서 그 코드를 넣었더니 맞았다.

https://abbiddo.tistory.com/59

웃긴 점은 제한에 저렇게 쓰여져 있어 들어가봤더니 2580문제에 대한 답이 있다.

넣어보니 진짜 맞는다.

근데 내가 푼 백트래킹보다 속도가 두 배정도 빠르다.

 

내가 푼 백트래킹은 위의 링크에 있다.입출력만 살짝 바뀐 거라 따로 설명은 안 하겠다.

문제에 있는 해답 코드에 대해 살펴봤다.

해당 코드는 아래와 같다.

#include <iostream>
using namespace std;
int a[10][10];
bool c[10][10];
bool c2[10][10];
bool c3[10][10];
int n=9;
int cnt=0;
int square(int x, int y) {
    return (x/3)*3+(y/3);
}
bool go(int z) {
    cnt += 1;
    if (cnt >= 10000000) {
        return true;
    }
    if (z == 81) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
        return true;
    }
    int x = z/n;
    int y = z%n;
    if (a[x][y] != 0) {
        return go(z+1);
    } else {
        for (int i=1; i<=9; i++) {
            if (c[x][i] == 0 && c2[y][i] == 0 && c3[square(x,y)][i]==0) {
                c[x][i] = c2[y][i] = c3[square(x,y)][i] = true;
                a[x][y] = i;
                if (go(z+1)) {
                    return true;
                }
                a[x][y] = 0;
                c[x][i] = c2[y][i] = c3[square(x,y)][i] = false;
            }
        }
    }
    return false;
}
int main() {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> a[i][j];
            if (a[i][j] != 0) {
                c[i][a[i][j]] = true;
                c2[j][a[i][j]] = true;
                c3[square(i,j)][a[i][j]] = true;
            }
        }
    }
    go(0);
    return 0;
}

 

c[10][10], c2[10][10], c3[10][10]:배열은 각각 행, 열, 그리고 3x3 에 숫자가 등장했는지를 나타내는 배열이다.

square 함수는 3x3 사각형의 번호를 반환하는 함수다.

go는 재귀 함수로 cnt 가 천만이 넘어가면 종료한다.

z가 현재 처리할 칸으로 x, y좌표를 계산한다.

해당 위치가 0이 아니라면 다음 칸으로 넘어간다.

0이라면 1 ~ 9를 채워보면서 행, 열, 3x3 사각형에 사용되지 않은 숫자라면 숫자를 채우고 재귀적으로 다음 칸을 진행한다.

 

내가 한 방식은 항상 2중 반복문을 돌며 배열을 확인해보는 것인데

위의 방식은 배열에 저장을 해 반복문을 사용하지 않았다.

이 점에서 시간 차이가 두 배 이상 나는 것 같다.

 

위가 위의 코드

아래가 내가 푼 코드