[백준 2239] 스도쿠 C++

2239번: 스도쿠

백트래킹

---

1. 문제풀이 아이디어

브루트포스 + 백트래킹 문제이다

현재 칸이 '0' 이라면 1 ~ 9까지의 숫자를 모두 대입해 보고, 대입한 숫자가 현재 칸에 들어가도 되는지 확인한다. 

현재 칸에 모든 숫자가 들어갈 수 없다면 현재 칸을 다시 0으로 만들고 이전 칸으로 돌아간다.

현재 칸이 '0'이 아니라면 다음 칸으로 넘어간다.

---

2. 코드 설명

<+7>~<+15>  숫자를 입력 받아 Map 배열에 넣는다.

<+17>~<+24> Map 상태를 보여준다.

<+27> ~ <+48> 현재 칸에 들어있는 숫자를 넣어도 룰에 어긋나지 않는지 확인한다.

                        가로, 세로를 먼저 확인하고, 현재 칸이 위치한 3x3 박스도 확인한다.

<+50>~<+70> 백트래킹(재귀)부분. 현재 열의 끝을 넘어가면 다음행 0열을 호출한다.

                      마지막 행에 도달하면 지금까지 구한 배열을 출력하고 강제종료.

<+61>~<+67> 문제풀이 아이디어에 제시된 내용을 그대로 구현함.

#include <iostream>
 
using namespace std;
 
int Map[10][10];
 
void input(){
    string line;
    for(int i = 0; i < 9; i++){
        cin >> line;
        for(int j = 0; j < 9; j++){
            Map[i][j] = line[j] - '0';
        }
    }
}
 
void show_Map(){
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            cout << Map[i][j];
        }
        cout << "\n";
    }
}
 
// Map에 1~9까지의 숫자를 넣어보고 룰에 어긋나면 false 반환
inline bool check_rule(int r, int c){
    // row, col check
    for(int i = 0; i < 9; i++){
        // row check
        if(Map[r][c] == Map[r][i] && i != c) return false;
        // col check
        if(Map[r][c] == Map[i][c] && i != r) return false;
    }
    
    int sr = (r / 3) * 3;
    int sc = (c / 3) * 3;
    
    // box check
    for(int i = sr; i < sr + 3; i++){
        for(int j = sc; j < sc + 3; j++){
            if(i == r && j == c) continue;
            if(Map[r][c] == Map[i][j]) return false;
        }
    }
    
    return true;
}
 
void solve(int r, int c){
    if(r == 9){
        show_Map();
        exit(0);
    }
    
    if(c == 9){
        solve(r + 1, 0);
        return;
    }
    
    if(Map[r][c] == 0){
        for(int i = 1; i <= 9; i++){
            Map[r][c] = i;
            if(check_rule(r, c)) solve(r, c+1);
        }
        Map[r][c] = 0;
    }
    
    else solve(r, c+1);
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve(0, 0);
    
    return 0;
}
 

476ms

Map[i][j] == 0인 경우에 매번 check_rule함수가 수행되고, 그 만큼 함수 호출에 따른 오버헤드가 커져서 남들보다 시간이 오래 걸리지 않았을까 생각이 든다

bool 형의 row[9] 배열, col[9] 배열, box[9] 배열을 하나씩 만들어서 함수 호출을 하지않고 넣고자 하는 숫자가 배열에 있는지 random access로 바로 확인을 해주는 방법을 사용한다면 시간을 많이 줄일 수 있지 않을까 생각해보았다.