Algorithm/Baekjoon

[Algorithm] Baekjoon 2239번 : 제출

MaxLevel 2023. 10. 31. 01:56

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

 

2239번: 스도쿠

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
int arr[9][9];
 
bool checkRow(int y, int x, int num)
{
    for (int i = y - 1; i >= 0; --i)
    {
        if (arr[i][x] == num) return false;
    }
 
    for (int i = y + 1; i < 9; ++i)
    {
        if (arr[i][x] == num) return false;
    }
 
    return true;
}
 
bool checkCol(int y, int x, int num)
{
    for (int i = x - 1; i >= 0; --i)
    {
        if (arr[y][i] == num) return false;
    }
 
    for (int i = x + 1; i < 9; ++i)
    {
        if (arr[y][i] == num) return false;
    }
 
    return true;
}
 
bool check33(int y, int x, int num)
{
    int startY = (y / 3) * 3;
    int startX = (x / 3) * 3;
 
    for (int i = startY; i < startY + 3; ++i)
    {
        for (int j = startX; j < startX + 3; ++j)
        {
            if (arr[i][j] == num) return false;
        }
    }
 
    return true;
}
 
void DFS(int y, int x)
{
    if (x == 9)
    {
        x = 0;
        ++y;
 
        if (y == 9)
        {
            for (int i = 0; i < 9; ++i)
            {
                for (int j = 0; j < 9; ++j)
                {
                    cout << arr[i][j];
                }
                cout << endl;
            }
 
            exit(0);
        }
    }
 
    if (arr[y][x] == 0)
    {
        for (int i = 1; i <= 9; ++i)
        {
            if (!checkRow(y, x, i)) continue;
            if (!checkCol(y, x, i)) continue;
            if (!check33(y, x, i)) continue;
 
            arr[y][x] = i;
            DFS(y, x + 1);
            arr[y][x] = 0;
        }
    }
    else
    {
        DFS(y, x + 1);
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 9; ++i)
    {
        string s;
        cin >> s;
        for (int j = 0; j < 9; ++j)
        {
            arr[i][j] = s[j] - '0';
        }
    }
 
    DFS(0, 0);
}
 
 cs

연습으로 풀어볼만한 백트래킹 문제이다.

스도쿠라는 게임에 조건에 맞게 숫자를 넣고 빼면서 완전탐색을 돌리면 된다.