반응형

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

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 스도쿠판을 입력받고, 백트래킹을 이용하여 모든 경우의 수를 체크합니다.

 

2. sero, garo, square 배열을 만들어 해당 줄과 칸에 숫자 존재 여부를 저장합니다.

 

3. 규칙에 맞게 스도쿠판이 채워지면 스도쿠판을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int arr[9][9];
int sero[9][10];
int garo[9][10];
int square[9][10];
bool flag = false;
 
void dfs(int num)
{
    if (flag) return;
    if (num == 81) {
        flag = true;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << arr[i][j] << ' ';
            }
            cout << '\n';
        }
    }
 
    int y = num / 9;
    int x = num % 9;
 
    if (arr[y][x] == 0) {
        for (int i = 1; i <= 9; i++) {
            if (sero[x][i] != 1 && garo[y][i] != 1 && square[(y / 3) * 3 + x / 3][i] != 1) {
                sero[x][i] = 1;
                garo[y][i] = 1;
                square[(y / 3) * 3 + x / 3][i] = 1;
                arr[y][x] = i;
                dfs(num + 1);
                sero[x][i] = 0;
                garo[y][i] = 0;
                square[(y / 3) * 3 + x / 3][i] = 0;
                arr[y][x] = 0;
            }
        }
    }
    else {
        dfs(num + 1);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> arr[i][j];
            if (arr[i][j] != 0) {
                sero[j][arr[i][j]] = 1;
                garo[i][arr[i][j]] = 1;
                square[(i / 3) * 3 + j / 3][arr[i][j]] = 1;
            }
        }
    }
 
    dfs(0);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22

+ Recent posts

티스토리툴바