백준 2580 스도쿠

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

골드4 백트래킹..결국못풀고 답을봐버렷다..

푸는방법도 각양각색인데

3 by 3 을체크하는부분에서 해멧다 ㅠ

메인 아이디어

1. 재귀 사용!
2. 행 , 열 , 3 by 3 검사하기
   2.1 검사에 실패했다면 0으로 바꿔주고 return 하기
   2.2 검사 성공했다면 채워넣고 다음으로
3. 출력하기

서브아이디어

1. 비어있는칸을 넣어서 전부 검사하지않고 queue에 꺼내서 처리하기 > 시간이매우줄어듬
2. StringBuilder에 넣고 메소드 종료해버리기

물론..반영은하지않았지만 이렇게 각양각색이다.. 아무튼 내코드는 다음과같다..

import java.io.*;
import java.util.*;

public class 스도쿠 {

	static int N;
	static int array[][];
	static int answer[][];
	static boolean visited[][];
	static int bcount;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = 9;
		array= new int[9][9];
		answer = new int[9][9];
		StringTokenizer st;
		bcount = 0;
		for(int i=0;i<9;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<9;j++) {
				int cur = Integer.parseInt(st.nextToken());
				array[i][j] = cur;
				if(cur==0) {
					bcount++;
				}
			}
		}
		System.out.println("bcount "+ bcount);
		start(0);
		
		for(int a=0;a<9;a++) {
			for(int b=0;b<9;b++) {
				System.out.print(answer[a][b]+" ");
			}
			System.out.println();
		}
	}
	
	public static void start(int count) {
		if(count==bcount) {
			//검증해보기
			for(int a=0;a<9;a++) {
				for(int b=0;b<9;b++) {
					answer[a][b] = array[a][b];
				}
			}
			return;
		}

		for(int i=0;i<9;i++) {
			for(int j=0;j<9;j++) {
				if(array[i][j]==0) {
					for(int n=1;n<10;n++) 
					{
						if(check(i,j,n)) {
						array[i][j]=n;
						start(count+1);
						}
					}
					
					array[i][j]=0;
					return;
					
				}
			}
		}
	}
	public static boolean check(int x, int y,int number) {
		
		//step vertical & horizontal check
		
		for(int i=0;i<9;i++) {
			if(array[i][y]==number || array[x][i]==number) return false;
		}
		
		int fx = (x/3)*3;
		int fy = (y/3)*3;
		
		for(int i=fx;i<fx+3;i++) {
			for(int j=fy;j<fy+3;j++) {
				if(array[i][j]==number) return false;
			}
		}
		
		return true;
	}
	

}

자바 292ms 제한인데.. 통과가되어서..ㅎㅎ;;