[백준/C++] 2239번 스도쿠

백준

---

🤔문제 이해

행과 열, 그리고 3x3의 작은 사각형 안에 1~9까지의 수가 중복없이 나오게 보드를 짜는 문제이다.

 

조건
보드 : 9 x 9
시간 : 2초
메모리 : 256MB

---

🔥풀이🔥

백트래킹 방식으로 값이 비어있는 부분에 넣을 수 있는 수 중에서 가장 작은 수부터 넣어보면서 처음으로 보드가 숫자로 다 채워질 수 있을 때를 출력하면 된다.

 

변수 

- bool width[i][num] : i번째 행에 num의 존재 유무

- bool length[i][num] : i번째 열에 num의 존재 유무

- bool square[i][num] : i번째 사각형에 num의 존재 유무

    - square의 경우 좌표가 (i, j)일 때 (i/3)*2 + (j/3)을 계산한 값이 몇번째 사각형인지 나타낸다.

 

재귀함수 solve (int i, int j)

- 현재 상태 : 스도쿠 보드에서의 현재 위치 (i, j)

- 다음 상태 : j+1이 보드 내부이면 solve(i, j+1), 그렇지 않으면 solve(i+1, 0)

- 진입 상태 : 보드의 첫 위치 (0, 0)

- 종료 상태 : 보드의 끝까지 숫자로 다 채운 경우

 

함수 vector<int> availableNumbers(int i, int j)

- (i, j)에 들어올 수 있는 숫자들을 반환

 

❌트러블 슈팅

처음엔 i==9일 때 즉, 보드가 다 채워졌을 때 출력하고 return을 해줬는데 그렇게 되면 가능한 여러 답들이 다 출력되게 되어 출력 초과가 났다. 그래서 보드가 처음으로 다 채워지면 즉, 여러 답 중 사전식으로 가장 앞선 답을 출력하고 나면 프로그램 자체를 종료시키는 exit(0); 명령어를 사용했다.

 

✍️ 후기

재귀함수의 return 부분을 유의해야겠다. 그리고 보드 내부에 들어갈 수 있는 수는 1~9까지로 비트마스크를 이용하게 되면 연산이 더 빨라질 것 같다.

---

#include <iostream>
#include <vector>

using namespace std;

int map[10][10];
bool width[10][10];
bool length[10][10];
bool square[10][10];
string x;

vector<int> availNumbers(int i, int j) {
    vector<int> tmp;
    int idx = (i / 3) * 3 + j / 3;
    for (int k = 1; k <= 9; k++) {
        if (!width[i][k] && !length[j][k] && !square[idx][k]) {
            tmp.push_back(k);
        }
    }
    return tmp;
}

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

void solve(int i, int j) {
    if (i == 9) {
        printMap();
        exit(0);
    }

    if (map[i][j] == 0) {
        vector<int> tmp = availNumbers(i, j);
        if (tmp.empty())
            return;
        for (int k = 0; k < tmp.size(); k++) {
            int num = tmp[k];
            int idx = (i / 3) * 3 + j / 3;
            map[i][j] = num;
            width[i][num] = true;
            length[j][num] = true;
            square[idx][num] = true;

            if (j < 8)
                solve(i, j + 1);
            else
                solve(i + 1, 0);

            map[i][j] = 0;
            width[i][num] = false;
            length[j][num] = false;
            square[idx][num] = false;
        }
    } else {
        if (j < 8)
            solve(i, j + 1);
        else
            solve(i + 1, 0);
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    for (int i = 0; i < 9; i++) {
        cin >> x;
        for (int j = 0; j < 9; j++) {
            map[i][j] = x[j] - '0';
            int num = map[i][j];
            if (num != 0) {
                width[i][num] = true;
                length[j][num] = true;
                int idx = (i / 3) * 3 + j / 3;
                square[idx][num] = true;
            }
        }
    }
    solve(0, 0);
}