[C++] 백준/Gold/2239. 스도쿠

문제 개요

• 문제 링크: 스도쿠 (2239)
• 9x9 스도쿠 퍼즐을 완성하는 전형적인 백트래킹 문제.
• 입력에서 0은 빈 칸을 나타내며, 이 빈 칸에 1부터 9까지 숫자를 채워야 한다.
• 사전순 출력: 가장 먼저 완성된 스도쿠를 출력.

 

문제 접근

이번 문제는 전형적인 백트래킹 문제로, 빈 칸에 가능한 숫자를 하나씩 채워넣으면서 모든 경우를 탐색하는 방식으로 해결할 수 있다.
다만 이번 문제는 입력이 9x9의 문자열 형태로 주어지기 때문에, 이를 처리하여 숫자로 변환하고,
각 빈 칸의 좌표를 따로 저장하여 백트래킹을 효율적으로 수행할 필요가 있다.
아래 코드는 입력을 처리하는 부분과 백트래킹의 구조를 살펴본다.

for (int i = 0; i < 9; i++) {
    string s; cin >> s;
    for (int j = 0; j < 9; j++) {
        v[i][j] = s[j] - '0';
        if (v[i][j] == 0) empties.push_back({i, j});
    }
}

여러 백트래킹 문제를 풀어보면서 느낀 점은, 비슷한 난이도의 백트래킹 문제는 큰 틀은 동일하고, 그 안의 세부적인 로직만 바꾸면 풀 수 있다는 것이다.
이번 문제 역시 그러한 전형적인 틀에서 벗어나지 않으며, 9x9의 배열에서 빈 칸을 기준으로 백트래킹을 시행한다.

 

지문 해석

문제를 읽으면서 한 번에 이해가 되지 않았던 문장이 있었다.

"답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다."

여기서 "사전식으로 앞선다"는 말이 직관적으로 와닿지 않아 여러 번 고민한 끝에 다음과 같이 이해했다.
"2차원 배열을 1차원으로 나열했을 때 생기는 81자리의 숫자가 가장 작은 것을 출력하라는 뜻이다."

여기서 중요한 점은 모든 경우를 다 해봐야 하는가?에 대한 의문이었다.
하지만 빈 칸의 순서와 빈자리에 숫자를 채워넣는 순서를 고정하면,
가장 먼저 완성된 경우가 사전식으로 가장 앞서는 경우임을 알 수 있다.
즉, 모든 경우를 탐색할 필요 없이, 백트래킹이 첫 번째로 완성한 결과가 정답이다.

 

코드 설명

유효성 검사 함수 (Check)

bool Check(int x, int y, int n) {
    for (int i = 0; i < 9; i++)
        if (v[y][i] == n || v[i][x] == n) return false;

    int xx = x < 3 ? 0 : x < 6 ? 3 : 6;
    int yy = y < 3 ? 0 : y < 6 ? 3 : 6;
    for (int i = yy; i < yy + 3; i++) {
        for (int j = xx; j < xx + 3; j++) {
            if (v[i][j] == n) return false;
        }
    }
    return true;
}

1. 행과 열 검사:
   • (x,y) 위치에서 숫자 n이 이미 같은 행 또는 열에 존재하는지 확인.
2. 3x3 블록 검사:
   • x,y가 속한 블록의 시작점을 계산하고, 해당 블록 내 숫자 n이 존재하는지 확인.
3. 모든 조건을 만족하면 true 반환, 그렇지 않으면 false.

 

백트래킹 함수 (Bt)

void Bt(int depth) {
    if (flag) return;
    if (depth == empties.size()) {
        flag = true;
        return;
    }

    auto pos = empties[depth];
    for (int i = 1; i <= 9; i++) {
        if (!Check(pos.second, pos.first, i)) continue;
        v[pos.first][pos.second] = i;
        Bt(depth + 1);
        if (flag) break;
        v[pos.first][pos.second] = 0;
    }
}

1. 종료 조건:
   • depth가 빈 칸의 개수와 같으면 모든 빈 칸이 채워진 상태.
   • flag를 true로 설정하고 종료.
2. 숫자 채우기:
   • 현재 빈 칸 좌표를 가져와 1부터 9까지 숫자를 순차적으로 시도.
   • 숫자를 채운 후 다음 깊이로 이동.
3. 백트래킹:
   • 만약 flag가 설정되었다면, 이미 답이 완성된 상태이므로 탐색 중단.
   • 그렇지 않다면, 이전 상태로 복구.

 

출력

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

• 완성된 스도쿠 배열을 출력.

 

코드 전체

#include <bits/stdc++.h>
using namespace std;

int v[9][9];
vector<pair<int, int>> empties;
bool flag = false;

bool Check(int x, int y, int n) {
    for (int i = 0; i < 9; i++)
        if (v[y][i] == n || v[i][x] == n) return false;

    int xx = x < 3 ? 0 : x < 6 ? 3 : 6;
    int yy = y < 3 ? 0 : y < 6 ? 3 : 6;
    for (int i = yy; i < yy + 3; i++) {
        for (int j = xx; j < xx + 3; j++) {
            if (v[i][j] == n) return false;
        }
    }
    return true;
}

void Bt(int depth) {
    if (flag) return;
    if (depth == empties.size()) {
        flag = true;
        return;
    }

    auto pos = empties[depth];
    for (int i = 1; i <= 9; i++) {
        if (!Check(pos.second, pos.first, i)) continue;
        v[pos.first][pos.second] = i;
        Bt(depth + 1);
        if (flag) break;
        v[pos.first][pos.second] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    for (int i = 0; i < 9; i++) {
        string s; cin >> s;
        for (int j = 0; j < 9; j++) {
            v[i][j] = s[j] - '0';
            if (v[i][j] == 0) empties.push_back({i, j});
        }
    }
    Bt(0);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << v[i][j];
        }
        cout << '\n';
    }
}