백준 g4 2239 스도쿠 c++

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

2239번: 스도쿠

문제

9*9의 배열이 주어진다. 0은 빈칸을 의미한다. 이때, 스도쿠를 채울 수 있게 답을 채워 출력한다.

답이 여러 개면, 81자리의 숫자가 제일 작은 것부터 출력한다.

문제는 항상 가능한 경우의 수만 주어진다.

 

풀이

빈칸이 있으면 1~9부터 넣어보면서 만약 해당 경우의 수가 불가능하면 backtracking으로 되돌리고, 다시 채우고 ... 반복하면 된다.

만약 빈칸이 모두 채워졌다면, 해당 스도쿠를 출력하면 된다.

 

가로/세로 확인은 쉽지만 3*3 box확인은 생각하기 조금 어려울 수 있다.

0 1 2 / 3 4 5 / 6 7 8

순으로 나뉘므로,

for (int i = 3 * (x / 3); i < 3 * (x / 3) + 3; i++) {

x/3의 몫 * 3으로 시작점을 정해주고, 그 시작점으로부터 3칸만 옮겨주면 된다.

 

주의할 점

for i,j 빈칸 찾기
	if 빈칸이면
    	for 1 ~ 9 넣어보기
    	
        만약 1~9 다 안 되면 return

 

빈칸에 1~9를 다 넣었는데 안 되면 return을 해주어야 한다.

마지막 줄의 return이 빠지면 그냥 빈칸이 0인 채로 다음 칸으로 넘어가게 되어 무한루프에 걸린다.

 

전체 코드

/*boj g4 2239 스도쿠*/
#include <iostream>
#define MAXN 105
using namespace std;

int N;
string str[10];
int board[9][9];
bool isEnd() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == 0) return false;
        }
    }
    return true;
}

bool isInHorizontal(int x, int y, int k) {
    for (int j = 0; j < 9; j++) {
        if (board[x][j] == k) return true;
    }
    return false;
}

bool isInVertical(int x, int y, int k) {
    for (int i = 0; i < 9; i++) {
        if (board[i][y] == k) return true;
    }
    return false;
}

bool isInBox(int x, int y, int k) {
    // 0 1 2 / 3 4 5 / 6 7 8
    int xCond = x / 3;
    int yCond = y / 3;

    for (int i = 3 * (x / 3); i < 3 * (x / 3) + 3; i++) {
        for (int j = 3 * (y / 3); j < 3 * (y / 3) + 3; j++) {
            if (board[i][j] == k) return true;
        }
    }
    return false;
}

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

void dfs(int x, int y) {
    // print();
    //   if () x, y가 끝이면?
    if (isEnd()) {
        print();
        exit(0);
    }
    for (int i = x; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != 0) continue;

            for (int k = 1; k <= 9; k++) {
                if (isInHorizontal(i, j, k)) continue;
                if (isInVertical(i, j, k)) continue;
                if (isInBox(i, j, k)) continue;

                board[i][j] = k;
                dfs(i, j);

                board[i][j] = 0;
            }

            return;
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < 9; i++) {
        cin >> str[i];
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            board[i][j] = str[i][j] - '0';
        }
    }
    dfs(0, 0);
}

 

 

 

예전에 2580 스도쿠라고 비슷한 문제가 있었는데 못 풀었고 아직도 내 백준에 맞히지 못한 문제로 남아있다.

지금은 거의 같은 문제를 슥 푸는 거 보면 성장하긴 했나보다