Problem
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
와.. 멍청이가 된거같아.. 앞으로 꾸준히 다시 풀어야겠다…
Check out this code in Victoria’s Gist. Please Comment my code in this link.