[BOJ] 2580. 스도쿠

백트래킹을 이용하여 빈칸의 숫자를 확인해가는 문제이다.

문제를 맨처음엔 행의 개념으로 접근하여 행마다 0의 갯수를 세어주고 다 채우면 다음행으로 가고를 반복하는 방식으로 접근하였는데 시간초과를 해결할수 없었다. 그래서 두가지 방법을 생각해냈다. 0의 위치만 List로 저장하는 방법과 행의 개념이 아니라 칸의 개념으로 depth를 81까지 확인하는 방법을 생각해냈다. 생각해낸 두번째 방법으로 구현을 직접 구현을 해보았고, check라는 함수를 만들어 행,열, 사각형 반경을 체크해주었다.

옛날에 풀었던 문제지만 다시 풀어보았다. 다시 풀어보니 접근법을 너무 어렵게 가져가서 힘든 부분이 있었다. 단순하게 생각하는게 필요할것 같다.

package online.practice;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_2580_스도쿠 {
    static int[][] map;
    static int N;
    static boolean find;
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =null;
        N=9;
        map=new int[N][N];            //맵
        
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        find=false;
        dfs(0);
        
    }
    
    static void dfs(int depth) {
        if(find==true)
            return;
        
        if(depth==N*N) {
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    System.out.print(map[i][j]+" ");
                }
                System.out.println();
            }
            find=true;
            return;
        }
        
        
        int row=depth/N;
        int col=depth%N;
        if(map[row][col]!=0) {
            dfs(depth+1);
        }else {
            for(int num=1;num<=9;num++) {
                if(check(row,col,num)==true) {
                    map[row][col]=num;
                    dfs(depth+1);
                    map[row][col]=0;
                }
            }
        }
    }
    
    static boolean check(int row,int col,int num) {
        for(int i=0;i<N;i++) {
            if(map[row][i]==num || map[i][col]==num)
                return false;
        }
        
        int startR=row/3*3;
        int startC=col/3*3;
        
        for(int i=startR;i<startR+3;i++) {
            for(int j=startC;j<startC+3;j++) {
                if(map[i][j]==num)
                    return false;
            }
        }
        
        return true;
    }
}