백준 2580 - 스도쿠 ( 재밌는 dfs 문제) c++

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

최소경로 문제가 아니므로 bfs가 아닌 dfs 문제이다.

오랜만에 dfs 백트래킹 문제를 만났는데,

n queen에서 공부했던 백트래킹의 기본에 대해서 생각해보면서 문제를 풀면 된다.

 

우선 해당하는 0의 열, 행, 그리고 사각형에 1~9까지를 넣는데, 넣을 때 그 행,열, 사각형에 이미 그 숫자가 있나 없나 검사를 한다. 

이때 검사를 할때, 각각 bool형 함수를 리턴해서 사용하는것 보다는, 각각 2차원 배열을 통해 메모이제이션을 진행하면

훨씬 빠르게 검사를 할 수 있다. (사실 내가 이 메모이제이션 부분을 생각해 내는게 아직 익숙치 않은데, 이 부분을 잘하면 실력이 늘 것 같단 생각이 든다.)

n queen에서는 다음 열에 놓여지는 퀸이 겹치는 행이나 겹쳐지는 대각선이 없는지를 검사하는 과정에 해당한다.

 

그 다음엔 백트래킹을 진행한다. 가능한 숫자가 있으면 일단 집어넣고 진행을 해서 불가능한 경우가 있으면 그 전에 넣었던 숫자를 다시 0으로 초기화하고 다시 숫자를 +1해서 탐색. 이를 count가 81이 될때까지 반복하면 된다.

 

#include <iostream>
using namespace std;
 
int map[9][9];
bool row[9][9];
bool column[9][9];
bool square[9][9];
 
void print(){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout<<map[i][j]<<" ";
        }
        cout<<"\n";
    }
}
 
void dfs(int count){
    if(count==81){
        print();
        exit(0); //한번만 출력해야 한다.
    }
    int y = count / 9;
    int x = count % 9;
 
    if(map[x][y]==0){
        for(int i=1; i<=9; i++){
            if(!row[x][i] && !column[y][i] && !square[(x/3)*3+(y/3)][i]){
                row[x][i] = true;
                column[y][i] = true;
                square[(x/3)*3+(y/3)][i] = true;
                map[x][y] = i;
                dfs(count+1);
                map[x][y]=0;
                row[x][i] = false;
                column[y][i] = false;
                square[(x/3)*3+(y/3)][i] = false;
 
            }
        }
    }
    else
        dfs(count+1);
}
 
int main(void){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cin>>map[i][j];
            if(map[i][j]){
                row[i][map[i][j]]=true;
                column[j][map[i][j]]=true;
                square[(i/3)*3+(j/3)][map[i][j]]=true;
            }
        }
    }
 
    dfs(0);
 
}