[BOJ] 스도쿠(2580)

[백준(BOJ)] 스도쿠(2580) C++

문제 : BOJ_2580번 스도쿠

입출력 형식만 살짝 다른 같은 문제로 BOJ_2239번 스도쿠도 있습니다.

문제 설명

백트래킹, dfs

완성되지 않은 스도쿠가 주어지고, 이를 완성하는 문제입니다.

스도쿠의 수가 확정되지 않은 곳은 0으로 입력되어 있고, 이 0들을 전부 채운 스도쿠판을 출력해야 합니다.

문제는 스페셜 저지이므로, 하나의 경우가 아닌 여러 경우가 답이 될 수 있는 스도쿠는 그중 하나를 출력하면 정답 처리가 됩니다.

dfs와 백트래킹을 이용해야 합니다.

---

Solution

입력 번호가 0인 곳의 좌표들을 하나하나 저장합니다.

저장된 좌표를 하나씩 dfs로 순회합니다.

이때 현재 순회 중인 곳에 맞는 번호가 있으면 다음 순회로 진행하고, 1~9 모든 번호가 다 중복된다면 이전 순회로 돌아가서 다른 수를 입력하는 백트래킹 방식을 사용해야 합니다.

0인 각 좌표를 돌면서 스도쿠의 규칙에 맞게 좌표의 세로축들, 가로축들에 인접한 곳들의 번호를 확인하여 체크합니다.

또한 각 좌표가 속한 3*3 사이즈의 사각형도 순회하며 번호를 확인하고 체크해 주어야 합니다.

---

Description

• 0인 각 좌표는 vector<pair<int, int>> zeroPoint를 사용해 저장했습니다.
• dfs의 인자는 (순회할 다음 x좌표, 순회할 다음 y좌표, 순회 횟수)로 만들었습니다.
• 각 순회마다 bool possible[10]의 bool형 배열을 만들어서 가능, 불가능한 수를 체크했습니다.

---

#include <iostream>
#include <vector>
using namespace std;
int map[10][10];
vector<pair<int, int>> zeroPoint;
int zeroPointCnt;
bool endSwc = false;
void dfs(int x, int y, int cnt) {
    if (endSwc) return;
    bool possible[10];
    for (int i = 1; i <= 9; i++) possible[i] = true;
    for (int i = 1; i <= 9; i++) {
        if (y == i) continue;
        possible[map[x][i]] = false;
    }
    for (int i = 1; i <= 9; i++) {
        if (x == i) continue;
        possible[map[i][y]] = false;
    }
    int xSt = 0;
    if (x % 3 == 0) xSt = x - 3;
    else xSt = x - (x % 3);
    int ySt = 0;
    if (y % 3 == 0) ySt = y - 3;
    else ySt = y - (y % 3);
    for (int i = xSt + 1; i <= xSt + 3; i++) {
        for (int j = ySt + 1; j <= ySt + 3; j++) {
            if (x == i && y == j) continue;
            possible[map[i][j]] = false;
        }
    }
    for (int i = 1; i <= 9; i++) {
        if (possible[i]) {
            if (cnt == zeroPointCnt) {
                map[x][y] = i;
                for (int i = 1; i <= 9; i++) {
                    for (int j = 1; j <= 9; j++) {
                        cout << map[i][j] << ' ';
                    }
                    cout << '\n';
                }
                endSwc = true;
                return;
            }
            else {
                map[x][y] = i;
                dfs(zeroPoint[cnt].first, zeroPoint[cnt].second, cnt + 1);
                map[x][y] = 0;
            }
        }
    }
}
int main(void) {
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cin >> map[i][j];
            if (map[i][j] == 0) {
                zeroPoint.push_back({ i,j });
                zeroPointCnt++;
            }
        }
    }
    dfs(zeroPoint[0].first, zeroPoint[0].second, 1);
    return 0;
}