2580_스도쿠

Concept & Idea

간단한 체크함수를 만듬으로써 문제를 비교적 간단하게 해결 할 수 있었다. check_s(3개짜리 정사각형 체크)함수는 구현하는데 생각을 좀 했어야 했다. 간단하게 row값과 col값을 3으로 나누고 거기서부터 3개씩 체크해주면 되는 파트였다.

• 처음에는 스도쿠에 빈 공간에 들어갈 숫자를 찾는데 10개짜리 배열을 계속 체크해주어야 한다고 생각했다. 그래서 배열을 계속 넘기고, 체크하고, 넘기고 다시 false인 요소의 값을 dfs돌려야 한다고 생각했는데, 확실히 감이 많이 죽은 것 같다.
• 그냥 For문을 10번씩 돌면서, 해당하는 숫자가 들어갈 수 있는가? 아닌가? 를 체크하면 간단하게 해결할 수 문제였다.
• DFS 안에 함수를 생각보다 복잡하고 비효율적으로 구현했었는데, 어차피 완전탐색으로 구현하는 거기 때문에 내 현재 index값만 알면 바로 그 다음값에 접근해서 탐색하면 되지, for문을 index부터 n까지 돌릴 필요가 없었다.

Code

#include <iostream>
#include <vector>
using namespace std;
int map[10][10];
vector<pair<int,int>> vec;
bool check_v(int y,int num){
    for(int i=0; i<9; i++) {
        if(num==map[i][y])
            return false;
    }
    return true;
}
bool check_h(int x,int num){
    for(int i=0; i<9; i++) {
        if(num==map[x][i])
            return false;
    }
    return true;
}
bool check_s(int x, int y, int num){
    x=x/3;
    y=y/3;
    for(int i=x*3; i<x*3+3; i++) {
        for(int j=y*3; j<y*3+3; j++) {
            if(map[i][j]==num)
                return false;
        }
    }
    return true;
}
void dfs(int x,int cnt){
    if(cnt==vec.size()){
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                cout<<map[i][j]<<" ";
            }
            cout<<endl;
        }
        exit(0);
    }
    for(int k=1; k<10; k++) {
        if(check_h(vec[x].first,k) && check_v(vec[x].second,k) && check_s(vec[x].first, vec[x].second, k)) {
            map[vec[x].first][vec[x].second]=k;
            dfs(x+1,cnt+1);
            map[vec[x].first][vec[x].second]=0;
        }
    }

}
int main() {
    for(int i=0; i<9; i++) {
        for(int j=0; j<9; j++) {
            cin>>map[i][j];
            if(map[i][j]==0) {
                vec.push_back({i,j});
            }
        }
    }
    dfs(0,0);
}

 

Fealing

앞으로 꾸준히 다시 풀어야겠다…