[백준,c++] 2580번 - 스도쿠

문제

2580번: 스도쿠

 

코드

#include <iostream>
#include <vector>
#include <memory.h>


using namespace std;

int N = 9;
int map[9][9];
vector<pair<int,int>> blank; // 0 좌표
bool flag = false;
int ans[9][9];


bool check(int a, int b) {
    
    //한줄 체크
    for (int i = 0; i < 9; i++) {
        if (map[i][b] == map[a][b] && i != a) return false; //행 확인
        if (map[a][i] == map[a][b] && i != b) return false; //열 확인
    }
    
    int new_a = a/3*3;
    int new_b = b/3*3;
    
    for(int i = new_a; i<new_a+3; i++){	// 3*3 확인
        for(int k = new_b; k<new_b+3; k++){
            if(a == i && b == k) continue;
            if(map[i][k] == map[a][b]) return false;
        }
    }
    return true;
}

void dfs(int idx){
    if(flag) return;
    
    if(idx == blank.size()){
        memcpy(ans, map, sizeof(map));
        flag = true;
        return;
    }
    
    int x = blank[idx].first;
    int y = blank[idx].second;
    for(int num = 1; num<=9; num++){
        map[x][y] = num;
        if(check(x,y)) dfs(idx+1);
        map[x][y] = 0;
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cin>>map[i][k];
            if(!map[i][k]) blank.push_back({i, k});
        }
    }
    dfs(0);
    
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cout<<ans[i][k] << ' ';
        }
        cout<<'\n';
    }
}

 

풀이

시간 초과가 계속 괴롭혔던 문제였습니다. 

미리 빈칸을 입력받고 빈칸을 기준으로 채워가면서 백트랙킹을 돌리는데, 스도쿠의 규칙을 만족할 때만 놓을 수 있는 조건으로 구현했습니다. 다만 스도쿠의 규칙을 확인하는 부분에서 계속 시간 초과가 발생했습니다.

처음에 작성했던 코드는 아래와 같은데, 행과 열을 확인하는 코드는 문제가 없으나 3*3을 확인하는 부분에서 계속 시간 초과가 발생해서 저 부분만 위 정답 코드처럼 바꿔 주었더니 정답이 떴습니다. 시간복잡도 측면에서는 똑같을 것 같은데, 아직 왜 시간초과가 발생하는지는 잘 모르겠습니다. 

#include <iostream>
#include <unordered_map>
#include <vector>
#include <memory.h>


using namespace std;

int N = 9;
int map[9][9];
vector<pair<int,int>> blank; // 0 좌표
bool flag = false;
int ans[9][9];

bool is_width_height_valid(int x, int y){
    int val = map[x][y];
    
    for(int i=0; i<9; i++){ // width
        if(i == y) continue;
        if(val == map[x][i]) return false;
    }
    
    for(int i=0; i<9; i++){ // height
        if(i == x) continue;
        if(val == map[i][y]) return false;
    }
    return true;
}


bool is_square_valid(int x, int y){
    
    if(x>=0 && x<3) x = 0;
    else if(x >=3 && x<6) x = 3;
    else x = 6;
    
    if(y>=0 && y<3) y = 0;
    else if(y >=3 && y<6) y = 3;
    else y = 6;
    
    unordered_map<int,int> cnt;
    for(int i=x; i<x+3; i++){
        for(int k=y; k<y+3; k++){
            if(!map[i][k]) continue;
            int val = map[i][k];
            if(cnt[val]) return false;
            cnt[val] = 1;
        }
    }
    
    return true;
}

void dfs(int idx){
    if(flag) return;
    
    if(idx == blank.size()){
        memcpy(ans, map, sizeof(map));
        flag = true;
        return;
    }
    
    int x = blank[idx].first;
    int y = blank[idx].second;
    for(int num = 1; num<=9; num++){
        map[x][y] = num;
        if(is_width_height_valid(x, y) && is_square_valid(x, y)){
            dfs(idx+1);
        }
        map[x][y] = 0;
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cin>>map[i][k];
            if(!map[i][k]) blank.push_back({i, k});
        }
    }
    cout<<'\n';
    dfs(0);
    
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cout<<ans[i][k] << ' ';
        }
        cout<<'\n';
    }
    
}