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


아이디어

  • 스도쿠 빈칸에 백트래킹으로 1부터 9까지 모두 넣어서 가능한지 확인
  • 이때 빈칸의 위치를 받아서 해당 빈칸만 백트래킹 해줌
  • 이때 가로, 세로, 주변 9칸에 숫자 들어갔는지 확인하는 배열 미리 사용해 빠르게 확인

시간복잡도 계산

  • 스도쿠 모든칸 : N일때( N=10)
    • O(10^N^2)
    • 시간 초과나겠지만, 가지치기가 될 수 있을거라고 예상하고 진행

자료구조

  • 스도쿠 맵 : int map[10][10]
  • 가로에 들어간 숫자 chk : bool row_chk[10][10];
  • 세로에 들어간 숫자 chk : bool col_chk[10][10];
  • 주변 9칸에 들어간 숫자 chk : bool rec_chk[5][5][10];

코드(C++)

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
#include <iostream>
#include <vector>
 
using namespace std;
typedef pair<int, int> pi2;
 
int map[10][10];
bool row_chk[10][10];
bool col_chk[10][10];
bool rec_chk[5][5][10];
vector<pi2> v;
 
void dfs(int num) {
    if(num == v.size()) {
        for(int j=0; j<9; j++) {
            for(int i=0; i<9; i++) {
                cout << map[j][i] << ' ';
            }
            cout << '\n';
        }
        exit(0);
    }
    
    int ey = v[num].first;
    int ex = v[num].second;
    
    for(int i=1; i<=9; i++) {
        if(row_chk[ey][i]) continue;
        if(col_chk[ex][i]) continue;
        if(rec_chk[ey/3][ex/3][i]) continue;
        
        row_chk[ey][i] = 1;
        col_chk[ex][i] = 1;
        rec_chk[ey/3][ex/3][i] = 1;
        map[ey][ex] = i;
        
        dfs(num+1);
        
        row_chk[ey][i] = 0;
        col_chk[ex][i] = 0;
        rec_chk[ey/3][ex/3][i] = 0;
        map[ey][ex] = 0;
        
        
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    fill(&row_chk[0][0], &row_chk[9][10], 0);
    fill(&col_chk[0][0], &col_chk[9][10], 0);
    fill(&rec_chk[0][0][0], &rec_chk[4][4][10], 0);
    
    for(int j=0; j<9; j++) {
        for(int i=0; i<9; i++) {
            cin >> map[j][i];
            if(map[j][i] == 0) v.push_back(make_pair(j,i));
            else {
                // 빈칸 아닐경우 이미 들어가있는 수 체크
                row_chk[j][map[j][i]] = 1;
                col_chk[i][map[j][i]] = 1;
                rec_chk[j/3][i/3][map[j][i]] = 1;
            }
        }
    }
    
    dfs(0);
    
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 원래값으로 바꿔주는것
    • 무조건 다음 depth로 나가는 것은 상관없는데,
    • if 문써서 체크한다음 다음 dfs로 나갈 경우
    • 모든 경우 통과되지 않으면 이전 depth로 돌아오게됨
    • 이때 0으로 초기화되지 않은 값이 영향을 미치게됨

'알고리즘 > 백준' 카테고리의 다른 글

백준 1707 이분 그래프  (0) 2021.04.22
백준 9466 텀 프로젝트  (0) 2021.04.22
백준 2458 키 순서  (0) 2021.04.20
백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20

+ Recent posts

티스토리툴바