[백준 알고리즘 -2580] 스도쿠 - java (백트래킹)

빈칸은 최대 81개이고 들어갈 수 있는 경우는 1부터 9까지이며 

입력을 받음과 동시에 상태 저장을 배열에 해두면 되기 때문에 상태 확인 시간 복잡도는 O(1)이다.

빈칸도 미리 저장해 둔 뒤 빈칸만 판별할 수 있기 때문에 완전 탐색으로 충분히 해결이 가능한 문제이다.

나는 Node라는 x, y라는 클래스와 인덱스 변수를 통해 0(빈칸)의 위치를 미리 저장해두었고

재귀호출을 통해 이 빈칸을 백트래킹으로 채워나가는 방법으로 문제를 해결하였다.

import java.util.ArrayList;
import java.util.Scanner;

class Main{
	   static boolean[][] check_col=new boolean[9][10];//행 검사
	   static boolean[][] check_row=new boolean[9][10];//열 검사
	   static boolean[][] check_box=new boolean[9][10];//박스 검사
	   
// arr=스도쿠, count= 전체 빈칸의 수, nodes=빈칸위치를 담고있는 리스트, idx=현재 탐색 중인 빈칸의 인덱스
		public static boolean sd(int[][] arr, int count, ArrayList<Node> nodes, int idx) {
			if(idx >= count) {//비어있는 칸을 모두 탐색했다면 출력
				for(int i=0; i<9; i++) {
					for(int j=0; j<9; j++) {
						System.out.print(arr[i][j]+" ");
					}
					System.out.println();
				}
				return true;//탐색 끝
			}
			Node node=nodes.get(idx);
			for(int i=1; i<=9; i++) {//1부터 9까지 모든 경우의 수 탐색
//promising?
				if(check_col[node.x][i]==true)
					continue;
				if(check_row[node.y][i]==true)
					continue;
				if(check_box[(node.x/3)*3+(node.y)/3][i]==true)
					continue;
				check_col[node.x][i]=true;
				check_row[node.y][i]=true;
				check_box[(node.x/3)*3+(node.y)/3][i]=true;
				
				arr[node.x][node.y]=i;
				
				if(sd(arr, count, nodes, idx+1))
					return true;//탐색 끝
//백트래킹			
				arr[node.x][node.y]=0;
				check_col[node.x][i]=false;
				check_row[node.y][i]=false;
				check_box[(node.x/3)*3+(node.y)/3][i]=false;				
			}
			
			return false;
		}
       public static void main(String[] args){
    	   Scanner scan=new Scanner(System.in);
    	   int[][] sd=new int[9][9];
    	 
    	   int count=0;
    	   ArrayList<Node> nodes=new ArrayList<Node>();
    	   
    	   for(int i=0; i<9; i++) {
    		   for(int j=0; j<9; j++) {
    			   sd[i][j]=scan.nextInt();
    			   if(sd[i][j]==0) {
    				   count++;
    				   nodes.add(new Node(i,j));
    			   }
    			   else {
    				   check_col[i][sd[i][j]]=true;
    				   check_row[j][sd[i][j]]=true;
    				   check_box[(i/3)*3+(j/3)][sd[i][j]]=true;
    			   }
    		   }
    	   }
    	   
    	   sd(sd, count, nodes, 0);
       }      
}
class Node{
	int x;
	int y;	
	Node(int x, int y){
		this.x=x;
		this.y=y;
	}
}