[JAVA] 백준 2580번 스도쿠

[HAVE TO DO]

STUDYING : JAVA

---

문제링크 : https://www.acmicpc.net/problem/2580

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] sudoku = new int[9][9]; // 스도쿠 판
	static ArrayList<Integer> point = new ArrayList<Integer>();
	static int zeroNum = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sudoku[i][j] = Integer.parseInt(st.nextToken());
				if(sudoku[i][j] == 0) {
					zeroNum++;
					point.add(i);
					point.add(j);
				}
			}
			if(i == 8) break;
			st = new StringTokenizer(br.readLine());
		}
		
		dfs(0, 0);
	}
	
	static boolean chk_row(int col, int num) {
		for (int row = 0; row < 9; row++) {
			if(sudoku[row][col] == num) return false;
		}
		return true;
	}
	
	static boolean chk_col(int row, int num) {
		for (int col = 0; col < 9; col++) {
			if(sudoku[row][col] == num) return false;
		}
		return true;
	}
	
	static boolean chk_box(int row, int col, int num) {
		int r = row - (row % 3);
		int c = col - (col % 3);
		
		for (int i = r; i < r + 3; i++) {
			for (int j = c; j < c + 3; j++) {
				if(sudoku[i][j] == num) return false;
			}
		}
		
		return true;
	}
	
	static boolean isPossible(int row, int col, int num) {
		if(chk_row(col, num) && chk_col(row, num) && chk_box(row, col, num)) {
			return true;
		} else return false;
	}
	
	static void dfs(int index, int cnt) {
		if(cnt == zeroNum) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(sudoku[i][j] + " ");
				}
				System.out.print("\n");
			}
		} else {
			int row = point.get(index);
			int col = point.get(index+1);
			for (int num = 1; num <= 9; num++) {
				if(isPossible(row, col, num)) {
					sudoku[row][col] = num;
					dfs(index+2, cnt+1);
					sudoku[row][col] = 0;
				}
			}
		}
	}
}

처음엔 이렇게 제출했는데 1% 뜨자마자 틀렸다고 떴다.

왜인지 찾아보니 경우의 수가 많으면 가능한 모든 경우의 수를 출력하기 때문이었다.

 

그래서 첫 번째 가능한 경우의 수를 출력한 후에 System.exit(0);으로 프로세스를 끝내버렸다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] sudoku = new int[9][9]; // 스도쿠 판
	static ArrayList<Integer> point = new ArrayList<Integer>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sudoku[i][j] = Integer.parseInt(st.nextToken());
				if(sudoku[i][j] == 0) {
					point.add(i);
					point.add(j);
				}
			}
			if(i == 8) break;
			st = new StringTokenizer(br.readLine());
		}
		
		dfs(0, 0);
	}
	
	static boolean chk_row(int col, int num) {
		for (int row = 0; row < 9; row++) {
			if(sudoku[row][col] == num) return false;
		}
		return true;
	}
	
	static boolean chk_col(int row, int num) {
		for (int col = 0; col < 9; col++) {
			if(sudoku[row][col] == num) return false;
		}
		return true;
	}
	
	static boolean chk_box(int row, int col, int num) {
		int r = row - (row % 3);
		int c = col - (col % 3);
		
		for (int i = r; i < r + 3; i++) {
			for (int j = c; j < c + 3; j++) {
				if(sudoku[i][j] == num) return false;
			}
		}
		
		return true;
	}
	
	static boolean isPossible(int row, int col, int num) {
		if(chk_row(col, num) && chk_col(row, num) && chk_box(row, col, num)) {
			return true;
		} else return false;
	}
	
	static void dfs(int index, int cnt) {
		if(cnt == (point.size() / 2)) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(sudoku[i][j] + " ");
				}
				System.out.print("\n");
			}
			System.exit(0);
		} else {
			int row = point.get(index);
			int col = point.get(index+1);
			for (int num = 1; num <= 9; num++) {
				if(isPossible(row, col, num)) {
					sudoku[row][col] = num;
					dfs(index+2, cnt+1);
					sudoku[row][col] = 0;
				}
			}
		}
	}

}

 

 

dfs를 사용해서 구현했고 0으로 입력된 곳만 탐색하는 방법을 선택했다.