[백준 2580] 스도쿠

문제풀이

너무 꼬아서 생각했다.. 

내가 너무 쉬운 스도쿠만 풀었는지 확실하게 유니크한 값들을 채워나가면 공백이 줄지 알고 공백들을 계속 돌려 유니크한 1개의 값을 채워나가는 방식으로 생각했는데 예외가 너무 많았다. 고려할게 2가지 이상인게 모두일때 그 방법은 무한루프 상태가 된다. 

 

그래서 남들 처럼 dfs 방법으로 풀었다.

 

자리확인은 원래 bool 배열로 해도 됐으나 그전에 짠 비트마스크 코드가 아까워 그대로 사용하였다. 하고보니 그냥 간단한 dfs문제였다.

소스코드

#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
queue<pair<int,int>> q;
 
int Map[9][9];
int set_row[9];
int set_col[9];
int set_square[3][3];
 
bool isPossible(int row, int col,int num){
    int union_num = set_row[row] | set_col[col] | set_square[row/3][col/3];
    
    if(union_num & (1<<num))
        return false;
    return true;
}
 
void dfs(int cnt){
    if(cnt==81){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                printf("%d ",Map[i][j]);
            }
            printf("\n");
        }
        exit(0);
    }
    
    int row = cnt/9;
    int col = cnt%9;
    
    if(Map[row][col])
        dfs(cnt+1);
    else{
        for(int i=1; i<=9;i++){
            if(isPossible(row,col,i)){
                Map[row][col] = i;
                set_row[row]+= (1<<i);
                set_col[col]+= (1<<i);
                set_square[row/3][col/3] += (1<<i);
                dfs(cnt+1);
                Map[row][col] = 0;
                set_row[row]-= (1<<i);
                set_col[col]-= (1<<i);
                set_square[row/3][col/3] -= (1<<i);
                
            }
        }
    }
    
    
}
 
int main() {
    
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            int input;
            scanf("%d",&input);
            Map[i][j] = input;
            if(input!=0){
                set_row[i]+= (1<<input);
                set_col[j]+= (1<<input);
                set_square[i/3][j/3] += (1<<input);
            }
        }
    }
    dfs(0);
 
    
    return 0;
}
 

 

 

문제 링크 : www.acmicpc.net/problem/2580

2580번: 스도쿠