(백준) 2580번 - 스토쿠

문제

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

풀이

행, 열, 3 X 3 영역에 중복된 숫자가 존재하지 않도록 백트래킹으로 수를 배치하는 문제이다.

코드

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

struct Coor {
    int x, y;
    Coor(int x, int y) : x(x), y(y) {}
};

int arr[9][9];
vector<Coor> zeros;

void printArr() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
}

bool row(int num, int x, int y) {
    for (int i = 0; i < 9; i++) {
        if (arr[x][i] == num) {
            return false;
        }
    }
    return true;
}

bool col(int num, int x, int y) {
    for (int i = 0; i < 9; i++) {
        if (arr[i][y] == num) {
            return false;
        }
    }
    return true;
}

bool square(int num, int x, int y) {
    int sx = (x / 3) * 3;
    int sy = (y / 3) * 3;

    for (int i = sx; i < sx + 3; i++) {
        for (int j = sy; j < sy + 3; j++) {
            if (arr[i][j] == num) {
                return false;
            }
        }
    }
    return true;
}

bool ok(int num, int x, int y) {
    return col(num, x, y) && row(num, x, y) && square(num, x, y);
}

void dfs(int cnt) {
    if (cnt == zeros.size()) {
        printArr();
        exit(0);
    }

    Coor cur = zeros[cnt];

    for (int i = 1; i <= 9; i++) {
        if (ok(i, cur.x, cur.y)) {
            arr[cur.x][cur.y] = i;
            dfs(cnt + 1);
            arr[cur.x][cur.y] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 0) {
                zeros.push_back(Coor(i, j));
            }
        }
    }

    dfs(0);
}

---

단, 방문 여부를 비트마스킹을 사용한다면 아래와 같이 작성할 수 있다.

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

struct Coor {
    int x, y;
    Coor(int x, int y) : x(x), y(y) {}
};

int arr[9][9];
vector<Coor> zeros;

int chk_row[9]; // i번째 행에 방문 체크 비트
int chk_col[9];
int chk_square[9];

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

void printArr() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
}

void dfs(int cnt) {
    if (cnt == zeros.size()) {
        printArr();
        exit(0);
    }

    int x = zeros[cnt].x;
    int y = zeros[cnt].y;
    int square_idx = get_square_idx(x, y);

    for (int i = 1; i <= 9; i++) {
        int mask = chk_row[x] | chk_col[y] | chk_square[square_idx];
        int cur = 1 << (i - 1);

        if ((mask & cur) == 0) {
            arr[x][y] = i;
            chk_row[x] ^= cur;
            chk_col[y] ^= cur;
            chk_square[square_idx] ^= cur;

            dfs(cnt + 1);

            arr[x][y] = 0;
            chk_row[x] ^= cur;
            chk_col[y] ^= cur;
            chk_square[square_idx] ^= cur;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 0) {
                zeros.push_back(Coor(i, j));
            }
            else {
                int num = arr[i][j];
                int cur = 1 << (num - 1);
                int square_idx = get_square_idx(i, j);

                chk_row[i] |= cur;
                chk_col[j] |= cur;
                chk_square[square_idx] |= cur;
            }
        }
    }

    dfs(0);
}

---

변수는 따로 주어지지 않았지만, 스토쿠 변의 길이를 $N$, 0의 개수를 $M$으로 가정하자.

시간복잡도

첫 번째 코드는 매 단계에서 행, 열, 3 X 3 영역을 검사한다. 이러한 검사 비용은 $O(3N)$이다. 또한 최악의 경우 $M$개의 빈 칸에 1 ~ 9까지의 숫자를 넣어보므로, $O(9^M)$이다. 따라서 전체 시간복잡도는 $O(N \cdot 9^M)$이다.

두 번째 코드는 반복문 없이 유효성을 검사하므로, 검사 비용은 $O(1)$이다. 단, 역시 탐색 과정에서 시간복잡도는 $O(9^M)$이다. 따라서 전체 시간복잡도는 $O(9^M)$이다.

공간복잡도

첫 번째 코드는 arr, zeros 벡터에서 $O(N^2)$, 재귀 스택의 깊이는 빈 칸의 개수와 동일하므로 $O(M)$이다. $N^2 \geq M$이므로 전체 공간복잡도는 $O(N^2)$이다.

두 번째 코드 역시 재귀 스택 깊이가 동일하므로 전체 공간복잡도는 $O(N^2)$이다.