[백준 2239] 스도쿠

 

 

 단순 구현문제이다. 직관적으로 떠오르는 로직을 그대로 적용하게 되면 자연스럽게 백트래킹과 적당한 분기처리를 통해 풀게 된다. 탐색시간을 최대한 줄이기 위해서, 나는 가로줄, 세로줄, 3*3칸에 대해서 특정 숫자가 등장했는지 여부를 저장해두는 배열을 따로 생성해 이용했다.

 

 본격적인 로직도 심플하게 작성했다. 빈 칸의 위치를 모두 저장해놓은 리스트를 만들고, 이를 바탕으로 백트래킹을 시작한다. 인덱스가 depth 값인(백트래킹 하는 함수의 파라미터)  빈 칸 정보를 가져와서 1~9까지 들어갈 수 있는 숫자를 찾는다. 이 과정은 미리 생성해둔 3개의 숫자 등장 배열을 이용하면 빠르게 처리할 수 있다. 들어갈 수 있는 숫자를 찾았다면 숫자 등장 배열에 등장 처리를 해준 뒤에, 스도쿠 배열에도 해당 값을 채운 후에 다음 depth에 대한 백트래킹을 재개한다.

 함수를 재귀적으로 호출한 뒤에는 숫자 등장 배열 및 스도쿠 배열을 원복시켜, 백트래킹으로 돌아왔을 때 다음 탐색에 영향을 주지 않도록 한다.

 이를 반복해서 목표하는 depth(빈 칸의 개수만큼 진행되었는지 확인하면 된다)에 도달하면 완성된 스도쿠 배열을 출력하고 종료한다. 처음에 빈 칸 배열을 채울 때 좌측 상단부터 우측 하단까지 차례대로 채웠고, 탐색 과정에서 1~9를 순서대로 탐색하기 때문에 문제 조건인 사전식으로 가장 앞선 케이스 출력 또한 자연스럽게 달성된다.

 

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> point;

bool rowN[9][10] = {false, };
bool colN[9][10] = {false, };
bool blockN[9][10] = {false, };

int matrix[9][9];
vector<point> blankPointList;
bool endFlag = false;

int getBlockNum(int x, int y) {
    return (y/3)*3 + x/3; 
}

void sudoku(int depth) {
    if(endFlag) return;

    if(depth == blankPointList.size()) {
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                cout << matrix[i][j];
            }
            cout << "\n";
        }
        endFlag = true;
        return;
    }

    int x = blankPointList[depth].second;
    int y = blankPointList[depth].first;

    int blockNum = getBlockNum(x, y);
    for(int i=1; i<=9; i++) {
        if(!rowN[y][i] && !colN[x][i] && !blockN[blockNum][i]) {
            rowN[y][i] = true;
            colN[x][i] = true;
            blockN[blockNum][i] = true;
            matrix[y][x] = i;

            sudoku(depth+1);

            matrix[y][x] = 0;
            rowN[y][i] = false;
            colN[x][i] = false;
            blockN[blockNum][i] = false;
        }
    }

}

int main() {

    for(int i=0; i<9; i++) {
        for(int j=0; j<9; j++) {
            char c;
            cin >> c;
            matrix[i][j] = c-'0';
            if(matrix[i][j]==0) {
                blankPointList.push_back({i, j});                          
            } else {
                rowN[i][matrix[i][j]] = true;
                colN[j][matrix[i][j]] = true;
                blockN[getBlockNum(j, i)][matrix[i][j]] = true;
            }
        }
    }

    sudoku(0);
}