[백준] 2239 - 스도쿠

[문제링크]

2239번: 스도쿠

 

0. x, y좌표에 val값이 들어갈 수 있으려면

  - 같은 행에 val이 존재해선 안되고

  - 같은 열에 val이 존재해선 안되고

  - 같은 3*3블록에 val이 존재해선 안된다

  - chk함수로 이를 판단

  - 하나의 행/열에서 1~9의 숫자는 한번씩만 등장하므로, boolean배열로 중복 여부를 판단한다

 

1. x,y의 값이 0일때, 1~9까지 가능한 모든 숫자를 넣어보면서 다음 단계로 진행한다

  - 0이 아니면 바로 다음으로 진행

 

2. 진행이 불가능하면 false반환, 다음 숫자를 시도

 

3. 모든 칸에 합당한 숫자가 채워져 cur값이 81까지 진행됬다면, 스도쿠가 완성된 것으로 true를 반환한다

 

4. 해답이 여러개 존재한다 해도, 1부터 9까지, 작은수를 우선해서 수행했으므로

  - 첫번째 해답은 항상 가장 작은 해답이다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	
	static int[][] map;
	static boolean[][]rowChk;
	static boolean[][]colChk;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = 9;
		map = new int[N][N];
		rowChk = new boolean[N][N+1];
		colChk = new boolean[N][N+1];
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j]=s.charAt(j)-'0';
				if(map[i][j]!=0) {
					rowChk[i][map[i][j]]=true;
					colChk[j][map[i][j]]=true;
				}
			}
		}
		
		rec(0);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sb.append(map[i][j]);
			}sb.append('\n');
		}System.out.println(sb);
		
	}
	static boolean rec(int cur) {
		if(cur==81)return true;
		int x = cur/9;
		int y = cur%9;
		if(map[x][y]==0) {
			for (int i = 1; i <= 9; i++) {
				if(chk(x,y,(x/3)*3, (y/3)*3, i)) {
					rowChk[x][i]=true;
					colChk[y][i]=true;
					map[x][y]=i;
					
					if(rec(cur+1))return true;
					
					rowChk[x][i]=false;
					colChk[y][i]=false;
				}
			}
			map[x][y]=0;
		}
		else {
			//이미 수가 있다
			return rec(cur+1);
		}
		return false;
	}
	
	static boolean chk(int row, int col, int x, int y, int val) {
		boolean ret=true;
		if(rowChk[row][val] || colChk[col][val])ret=false;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if(map[x+i][y+j]==val)ret=false;
		return ret;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면