[ 백준 / 2580 ] 스도쿠 ( 자바 )

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

 

기본적으로 알고 있는 스도쿠의 룰과 완전 똑같다. 게다가 정답이 없는 경우는 주어지지 않는다니, 첫번째로 정답이 나오는 것을 출력하고 종료하면 된다. (0,0)부터 (N,N)까지 계속 DFS로 들어간다.

 

그 이후, 가로, 세로, 9칸의 정사각형 3개에 대해서 어떤 숫자가 들어갈 수 있는지 검사한다. 이것을 Set에 담는다.

Set에 담긴 값들을 하나씩 대입해 보면서 가로, 세로, 9칸의 정사각형에 모두 만족하는지 확인한다.

가능하면 다시 다음 칸을 위한 DFS로 들어가고, 불가능하면 다른 숫자들을 넣어본다.

backtracking은 내가 바꾼 하나의 숫자를 다시 원래대로 돌려놓는 것이다.

여기서는 visited가 전혀 필요가 없다. 방몬을 했는지 안했는지는 의미가 없다.

 

분명 내가 만든 알고리즘은 통과했지만 시간이 오래 걸렸다. 어느 부분에서 줄일 수 있을까? 

 

//2580 스도쿠
import java.util.*;
public class Main {

	static int[][] array = new int[9][9];
	static boolean[] visited;
	static boolean isFinished=false;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		int cnt=0;
		for(int i=0;i<9;i++) {
			for(int j=0;j<9;j++) {
				array[i][j] = sc.nextInt();
				if(array[i][j]==0) cnt++;
			}
		}
		DFS(cnt);
	}
	
	public static void DFS(int cnt) {
		if(isFinished==true) return;
		
		//꽉찼다면 종료
		if(cnt==0) {
			for(int i=0;i<9;i++) {
				for(int j=0;j<9;j++) {
					System.out.print(array[i][j]+" ");
				}
				System.out.println();
			}
			isFinished=true;
			return;
		}
		
		//(0,0)부터 (N,N) 까지 검사해서 선착순으로 좌표 얻기
		int[] loc = new int[] { -1, -1 };
		for(int i=0;i<9;i++) {
			for(int j=0;j<9;j++) {
				if(array[i][j]==0) {
					loc[0]=i;
					loc[1]=j;
					break;
				}
			} if(loc[0]!=-1) break;
		}
		
		Set<Integer> set = new HashSet<>();
		
		int x = loc[0];
		int y = loc[1];
		
		//가로 확인 후 값 넣기
		visited = new boolean[10];
		for(int j=0;j<9;j++) {
			visited[array[x][j]]=true;
		}
		
		for(int i=1;i<=9;i++) {
			if(visited[i]==false) set.add(i);
		}
		
		//세로 확인 후 값 넣기
		visited = new boolean[10];
		for(int i=0;i<9;i++) {
			visited[array[i][y]]=true;
		}
		
		for(int i=1;i<=9;i++) {
			if(visited[i]==false) set.add(i);
		}
		
		//네모 확인 후 값 넣기
		int[] newLoc = find(x,y);
		visited = new boolean[10];
		for(int i=newLoc[0];i<=newLoc[2];i++) {
			for(int j=newLoc[1];j<=newLoc[3];j++) {
				visited[array[i][j]]=true;
			}
		}
		
		for(int i=1;i<=9;i++) {
			if(visited[i]==false) set.add(i);
		}
		
		// 가로, 세로, 네모 검사해서 가능한 숫자들 list에 넣기
		// 세가지를 검사했는데, 한가지만 나오는 곳이 있다면 그 번호만 사용하면 된다.

		// 가능한 숫자 없다면 종료 ( 이 경우는 없다고 문제에서 주어져 있다.)
		for(int val : set) {
			if(check(val, loc[0], loc[1])) {
				array[loc[0]][loc[1]] = val;
				DFS(cnt-1);
				array[loc[0]][loc[1]] = 0;
			}
		}
	}
	
	public static boolean check(int val, int x, int y) {
		//가로 검사
		visited = new boolean[10];
		for(int j=0;j<9;j++) {
			visited[array[x][j]] = true;
		}
		if(visited[val]==true) return false;
		
		
		//세로검사
		visited = new boolean[10];
		for(int i=0;i<9;i++) {
			visited[array[i][y]] = true;
		}
		if(visited[val]==true) return false;
		
		//네모 검사
		visited = new boolean[10];
		int[] loc = find(x,y);
		for(int i=loc[0];i<=loc[2];i++) {
			for(int j=loc[1];j<=loc[3];j++) {
				visited[array[i][j]]=true;
			}
		}
		if(visited[val]==true) return false;
		
		return true;
	}
	
	public static int[] find(int x, int y) {
		if(x>=0 && x<=2 && y>=0 && y<=2) return new int[] {0,0,2,2};
		if(x>=3 && x<=5 && y>=0 && y<=2) return new int[] {3,0,5,2};
		if(x>=6 && x<=8 && y>=0 && y<=2) return new int[] {6,0,8,2};
		
		if(x>=0 && x<=2 && y>=3 && y<=5) return new int[] {0,3,2,5};
		if(x>=3 && x<=5 && y>=3 && y<=5) return new int[] {3,3,5,5};
		if(x>=6 && x<=8 && y>=3 && y<=5) return new int[] {6,3,8,5};
		
		if(x>=0 && x<=2 && y>=6 && y<=8) return new int[] {0,6,2,8};
		if(x>=3 && x<=5 && y>=6 && y<=8) return new int[] {3,6,5,8};
		if(x>=6 && x<=8 && y>=6 && y<=8) return new int[] {6,6,8,8};
		return null;
	}
	 

}