[BOJ 2239] 스도쿠 (Java)

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

2239번: 스도쿠

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

public class Main_BOJ_2239 {
	static int[][] map=new int[10][10];
	static int[][] row=new int[10][10];
	static int[][] col=new int[10][10];
	static int[][] square=new int[10][10];
	static int cnt=0;
	static ArrayList<int[]> toFill=new ArrayList<>();
	static String answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		for (int i=1; i<=9; i++) {
			String s=br.readLine();
			for (int j=1; j<=9; j++) {
				int num=s.charAt(j-1)-'0';
				map[i][j]=num;
				if (num!=0) {
					row[i][num]=1;
					col[j][num]=1;
					square[checkSquareNum(i,j)][num]=1;
				}
				else {
					toFill.add(new int[] {i,j});
					cnt++;
				}
			}
		}
		backtracking(0);
		for (int i=0; i<81; i+=9) {
			System.out.println(answer.substring(i,i+9));
		}
	}
	
	private static boolean backtracking(int n) {
		if (n==cnt) {
			StringBuilder sb=new StringBuilder("");
			for (int i=1; i<=9; i++) {
				for (int j=1; j<=9; j++) {
					sb.append(map[i][j]);
				}
			}
			answer=sb.toString();
			return true;
		}
		int r=toFill.get(n)[0];
		int c=toFill.get(n)[1];
		for (int i=1; i<=9; i++) {
			if (row[r][i]==0 && col[c][i]==0 && square[checkSquareNum(r,c)][i]==0) {
				mark(r,c,i,1);
				if (backtracking(n+1)) return true;
				mark(r,c,i,0);
			}
		}
		return false;
		
	}
	
	private static void mark(int r, int c, int i, int val) {
		row[r][i]=val;
		col[c][i]=val;
		square[checkSquareNum(r,c)][i]=val;
		if (val==1) map[r][c]=i;
		else map[r][c]=0;
	}

	private static int checkSquareNum(int r, int c) {
		if (r>=1 && r<4) {
			if (c>=1 && c<4) return 1;
			else if (c>=4 && c<7) return 2;
			else return 3;
		}
		else if (r>=4 && r<7) {
			if (c>=1 && c<4) return 4;
			else if (c>=4 && c<7) return 5;
			else return 6;
		}
		else {
			if (c>=1 && c<4) return 7;
			else if (c>=4 && c<7) return 8;
			else return 9;
		}
	}

}

백트래킹 문제.

row 배열, col배열, square 배열을 따로 두어서 현재 넣으려고 하는 (row, col, square)에서  i번째 (row, col, square)에 현재 숫자가 있는지 체크하도록 했다.

 

나는 0인 것을 모아서 그것만 backtracking을 돌렸는데,

다른 분들의 코드를 보니 81개를 다 돌면서, 만약 map[row][col]이 0이 아니면 backtracking(i+1) 하는 식으로 다음번째로 넘겨주고 0이면 탐색 작업을 수행하는 식으로 했다. 

 

또한 checkSquareNum 함수를 쓸 필요 없이, (r/3)*3+(c/3) 으로 정사각형 번호를 나타낼 수 있다.