백준 2239번 [스도쿠](C++) -yes6686- 티스토리

백준 문제 풀이: 2239 [스도쿠]

---

문제 링크: https://www.acmicpc.net/problem/2239

문제 설명:

9x9 크기의 스도쿠 퍼즐이 주어졌을 때, 규칙에 따라 퍼즐을 완성하는 문제입니다. 스도쿠의 규칙은 다음과 같습니다:

• 각 행에는 1부터 9까지의 숫자가 중복 없이 포함되어야 합니다.
• 각 열에는 1부터 9까지의 숫자가 중복 없이 포함되어야 합니다.
• 각 3x3 박스에도 1부터 9까지의 숫자가 중복 없이 포함되어야 합니다.

---

문제 해결 코드

#include <iostream>
#include <cstring>
using namespace std;

int arr[10][10];
int c1[10][10]; // 행 검사
int c2[10][10]; // 열 검사
int c3[10][10]; // 박스 검사
int ch = 0;

void dfs(int x, int y) {
    if (ch) return;

    if (x == 10) {
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                cout << arr[i][j];
            }
            cout << '\n';
        }
        ch++;
        return;
    }

    if (arr[x][y]) {
        if (y == 9) dfs(x + 1, 1);
        else dfs(x, y + 1);
        return;
    }

    for (int i = 1; i <= 9; i++) {
        if (!c1[x][i] && !c2[y][i] && !c3[((x - 1) / 3) * 3 + ((y - 1) / 3) + 1][i]) {
            arr[x][y] = i;
            c1[x][i] = c2[y][i] = c3[((x - 1) / 3) * 3 + ((y - 1) / 3) + 1][i] = 1;
            if (y == 9) dfs(x + 1, 1);
            else dfs(x, y + 1);
            c1[x][i] = c2[y][i] = c3[((x - 1) / 3) * 3 + ((y - 1) / 3) + 1][i] = 0;
            arr[x][y] = 0;
        }
    }
}

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

    string s[9];
    for (int i = 0; i < 9; i++) {
        cin >> s[i];
        for (int j = 0; j < 9; j++) {
            arr[i + 1][j + 1] = s[i][j] - '0';
        }
    }

    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (arr[i][j]) {
                int box = ((i - 1) / 3) * 3 + ((j - 1) / 3) + 1;
                c1[i][arr[i][j]] = c2[j][arr[i][j]] = c3[box][arr[i][j]] = 1;
            }
        }
    }

    dfs(1, 1);
}

예제

입력:
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079

출력:
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

---

코드 설명

• 행/열/박스 체크 배열: 각 숫자가 특정 행, 열, 박스에 이미 사용되었는지 저장합니다.
• DFS 탐색: 스도쿠 퍼즐의 빈칸을 하나씩 채워가며 가능한 숫자를 대입합니다. 불가능할 경우 백트래킹합니다.
• 정답 출력: 첫 번째 가능한 정답을 찾으면 출력하고 종료합니다.

시간 복잡도

• 최악의 경우 O(9^81)의 경우의 수를 검사하지만, 백트래킹과 가지치기를 통해 탐색 범위를 줄입니다.

---

결과

이 코드는 DFS와 백트래킹을 이용해 스도쿠 퍼즐을 정확히 풀이합니다. 입력 데이터를 기반으로 유효한 결과를 출력하며, 최적화된 가지치기를 통해 탐색 속도를 높였습니다.