백준 2239 C++

풀다 만 스도쿠 빈칸 채우기

#include <iostream>

using namespace std;

int arr[10][10];
bool row[10][10], col[10][10], box[10][10];

bool solve(int y, int x) {
    if (y == 9 && x == 0) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << arr[i][j];
            }
            cout << endl;
        }
        return true;
    }

    if (!arr[y][x]) {
        for (int i = 1; i <= 9; i++) {
            if (row[y][i] || col[x][i] || box[(y / 3) * 3 + x / 3][i]) continue;
            row[y][i] = true;
            col[x][i] = true;
            box[(y / 3) * 3 + x / 3][i] = true;
            arr[y][x] = i;
            if (solve(y + (x + 1) / 9, (x + 1) % 9)) {
                return true;
            }
            row[y][i] = false;
            col[x][i] = false;
            box[(y / 3) * 3 + x / 3][i] = false;
            arr[y][x] = 0;
        }
        return false;
    } else {
        return solve(y + (x + 1) / 9, (x + 1) % 9);
    }
}

int main() {
    ios::sync_with_stdio(false);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%1d", &arr[i][j]);  // 띄어쓰기 없는 정수 1자리씩 입력받기
            row[i][arr[i][j]] = true;
            col[j][arr[i][j]] = true;
            box[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
        }
    }

    if (solve(0, 0)) {
        return 0;  // solve 함수의 리턴값이 true이면 프로그램 종료
    }
}

백트래킹(backtracking)

• 문제의 해를 찾아가는 과정 중 특정 시점에서 더 이상 해를 찾을 가능성이 없다고 판단하면, 그 이전 단계로 돌아가 다른 가능성을 탐색하는 알고리즘
• 주로 모든 가능한 해를 탐색하는 경우에 사용
• 해를 찾기 위해 시도한 경로가 올바르지 않다고 판단되면 돌아가서 다른 경로를 탐색 => 재귀 사용