백준 2580 스도쿠
본문 바로가기
알고리즘 모음집/알고리즘 (Algorithm)

백준 2580 스도쿠

by KyeongMin 2019. 7. 4.
728x90
반응형

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

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3

www.acmicpc.net

스도쿠 문제는 말 그대로 빈칸인 스도쿠를 주면 한개의 정답을 입력해서 출력해주라는 문제입니다.

문제를 봤을때 백트래킹을 이용해야한다 생각이 드는 문제였습니다.

하지만 과연 백트래킹을 돌려도 시간초과가 나지 않을까? 의문인 문제였습니다.

그래서 처음에선 2차원배열 백트래킹을 했는데 결과는....

시간초과가 났습니다.

 

그래서 예전 백트래킹 문제에서 백준에 치킨배달이라는 문제에서 필요한 인덱스를 

구조체배열을 사용해서 저장을 하고 그 인덱스만 이용하영 백트래킹을 하는 방식으로 

문제를 진행하였습니다.

 

그리고 이 문제에서 가장 중요한점은 한번만 결과값이 나오게 하라는것이였습니다.

본문에서는 두가지 방식으로 백트래킹 재귀 방식에서 한번만 나오게 하는법도 같이

소개하겠습니다.

 

스도쿠 소스코드를 보기전에 스도쿠란 무엇인가?

사이트에서도 잘 설정했지만 간단히 말하자면

 초록색 원이 칠해져있는 5를 넣는 위치에 가로 세로 방향으로 칠해진 노란색 길에 같은 수가 없어야하고

빨강 9칸의 네모칸에도 중복이 없이 1-9까지 숫자가 들어가야하는 규칙을 가지고 있습니다.

처음 가로 세로 방향을 확인하기위한 소스는

위의 그림과 같이 하면 되는데 

정사각형 9칸 네모를 확인을 처음에는 노가다로 했습니다.

그소스는 

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
if (y == 0) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 1) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 2) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)//3번구역
    {
        for (int i = 0; i < 3; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 3) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 4) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 5) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)//3번구역
    {
        for (int i = 3; i < 6; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 6) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 7) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)// 3번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
if (y == 8) {
    if (x == 0 || x == 1 || x == 2)// 1번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 3 || x == 4 || x == 5)// 2번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 3; j < 6; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
    if (x == 6 || x == 7 || x == 8)//3번구역
    {
        for (int i = 6; i < 9; i++) {
            for (int j = 6; j < 9; j++) {
                if (y == i && x == j)continue;
                if (Sudoku[i][j] == num)return false;
            }
        }
    }
}
 
 
노가다로 한개 구역식 인덱스 보고 설정하였습니다. 이렇게 해도 통과는 하는데 소스코드가 길어져서 한번에
합쳐보았습니다.
 
1
2
3
4
5
6
7
    int cy = y / 3;
    int cx = x / 3;
    for (int i = cy * 3; i < (cy * 3+ 3; i++) {
        for (int j = cx *3; j < (cx * 3+ 3; j++) {
            if (Sudoku[i][j] == num) return false;
        }
    }
 
 

대신 배열 인덱스를 (0,0)~(8,8) 일때 가능한 소스입니다.

두개 소스를 잘 비교해서 보면 이해가 되실껍니다.

 

라스트. 전체소스를 보여드리겠습니다.

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
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int Sudoku[9][9];
int N;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Sudo {
    int y, x;
};
Sudo board[81];
bool chk(int y, int x, int num) {
    //네방향 검사 
    for (int dir = 0; dir < 4; dir++) {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        while (0 <= ny && ny < 9 && 0 <= nx && nx < 9) {
            if (Sudoku[ny][nx] == num) return false;
            ny += dy[dir];
            nx += dx[dir];
        }
    }
    int cy = y / 3;
    int cx = x / 3;
    for (int i = cy * 3; i < (cy * 3+ 3; i++) {
        for (int j = cx *3; j < (cx * 3+ 3; j++) {
            if (Sudoku[i][j] == num) return false;
        }
    }
    return true;
}
void dfs(int idx) {
    if (idx == N) {
 
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    printf("%d ", Sudoku[i][j]);
                }
                printf("\n");
            }
            exit(0);
    }
        for (int num = 1; num <= 9; num++) {
            if (chk(board[idx].y, board[idx].x, num)) {
                Sudoku[board[idx].y][board[idx].x] = num;
                dfs(idx + 1);
                Sudoku[board[idx].y][board[idx].x] = 0;
            }
        }
}
 
int main(void)
{
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%d"&Sudoku[i][j]);
            if (Sudoku[i][j] == 0) {
                board[N].y = i;
                board[N].x = j;
                N++;
            }
        }
    }
    dfs(0);
    return 0;
}
 

의외로 간단한 소스같지만 좀 걸렸습니다.

여기서 마지막으로 한번만 출력을 하는게 포인트 인데 어떻게 했는지 알려드리자면 

헤더파일 #include<stdlib.h> 를 선언하고 exit(0)하게되면 되고, 헤더파일을 못쓰는데 그러면 방법이 없나?

하는분들도 계실수 있으므로 그렇다면 아래와 같이 쓰면됩니다.

 

flag 변수를 하나 선언하고 무조건 return 시키는 형식으로 해도 같은 결과가 나오니 참고해 주세요.

47분전이 exit(0);

32분전이 flag=1  return;

확실히 exit(0) 바로 끝내는것이 빠른걸 알수있습다. 물론 8ms 차이라 별차이가 없지만...

 

오늘도 긴글 읽어주시느라 고생하셨습니다. 감사합니다.

 

 

728x90
반응형

댓글