백준 2580 스도쿠

문제링크 : 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++)

#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;
}
 

문제유형

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