BOJ 2239 : 스도쿠

3줄요약

• 백트래킹
• 빡구현

 

서론

 

이 문제를 보고 처음에 난감했었다. 이 문제가 어떻게 골드 4인지 모를 만큼 감이 안 잡혔다. 이 문제를 브루트포스로 풀면 최대 O(9^81) 의 시간복잡도가 나오기 때문에, 이 문제는 브루트 포스로 풀 수 없다. 하지만, 백트래킹을 잘 하면 1억번의 연산 밑으로 해결할 수 있다는 생각이 들어 실행에 옮겼다.

본론

 

이 문제는 사전순으로 앞서는 것을 출력해야 하기 때문에, 체크를 다음의 순서로 해야 한다.

1	2	3	4	5	6	7	8	9
10	11	12	13	14	15	16	17	18
19	20	21	22	23	24	25	...

다음의 순서대로 진행하되, 그 자리에 숫자를 넣었을 때 안되는 경우를 미리 체크해 주면서 백트래킹을 실행하면, 문제가 풀린다. 코드는 밑에 있다.

 

 

#include <iostream>
#include <string>

using namespace std;

int sudoku[9][9];
int d[9][2][2] = { { {0, 3}, {0, 3} }, { {3, 6}, {0, 3} }, { {6, 9} , {0, 3} }, 
{ {0, 3}, {3, 6} }, { {3, 6}, {3, 6} }, { {6, 9} , {3, 6} }, 
{ {0, 3}, {6, 9} }, { {3, 6}, {6, 9} }, { {6, 9} , {6, 9} } };
int g[9] = { 0, 0, 0, 1, 1, 1, 2, 2, 2 };
bool ended = false;


void solve(int x, int y, int num, int nowsudoku[9][9]) {
    
    if (ended) return;

    for (int i = 0; i < 9; i++) {
        if (nowsudoku[i][y] == num) return;
        if (nowsudoku[x][i] == num) return;
    }

    int op = g[y] * 3 + g[x];
    int fromx = d[op][0][0]; int tox = d[op][0][1]; int fromy = d[op][1][0]; int toy = d[op][1][1];
    for (int i = fromx; i < tox; i++) {
        for (int j = fromy; j < toy; j++) {
            if (nowsudoku[i][j] == num) return;
        }
    }

    int newsudoku[9][9];
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            newsudoku[i][j] = nowsudoku[i][j];
        }
    }
    newsudoku[x][y] = num;

    int nxt[2] = { -1, -1 }; int cnt = 0;
    for (int i = 0; i < 9; i++) {
        bool endloop = false;
        for (int j = 0; j < 9; j++) {
            if (newsudoku[i][j] == 0) {
                nxt[0] = i; nxt[1] = j; endloop = true; break;
            }
        }
        if (endloop) break;
    }

    if (nxt[0] == -1 || nxt[1] == -1) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = newsudoku[i][j];
            }
        }
        ended = true;
        return;
    }

    for (int i = 1; i <= 9; i++) {
        solve(nxt[0], nxt[1], i, newsudoku);
    }
    return;
}

int main() {

    for (int i = 0; i < 9; i++) {
        string s; cin >> s;
        for (int j = 0; j < 9; j++) {
            sudoku[i][j] = s[j] - 48;
        }
    }

    int initialize[2];
    for (int i = 0; i < 9; i++) {
        bool endloop = false;
        for (int j = 0; j < 9; j++) {
            if (sudoku[i][j] == 0) {
                initialize[0] = i; initialize[1] = j; endloop = true; break;
            }
        }
        if (endloop) break;
    }

    for (int i = 1; i <= 9; i++) solve(initialize[0], initialize[1], i, sudoku);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) { if (sudoku[i][j] == 0) { printf("IMPOSSIBLE\n"); return 0; } printf("%d", sudoku[i][j]); }
        printf("\n");
    }
}

 

 

결론

 

구현 연습도 했고, 실용성이 전혀 없는 다른 백준 문제와는 달리 이 문제는 내 책장에 있는 스도쿠 문제집을 풀 수 있기에 유용하게 사용할 수 있다.

 

난이도(개인적): Gold III

난이도(객관적): Gold IV

 

Contact: How2Contact (tistory.com)