[백준] 스도쿠 2580 - JAVA

문제

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

2580번: 스도쿠

 

풀이

스도쿠는 가로, 세로, 3*3 내 사각형에서 같은 숫자가 있으면 안된다.

따라서 세가지를 체크해야 된다.

1. 가로

for(int i=0;i<9;i++) {
	if(board[r][i] == val)
	return false;
}

2.세로

for(int i=0;i<9;i++) {
	if(board[i][c] == val)
		return false;
}

3. 사각형

int sr = (r/3)*3;
int sc = (c/3)*3;
		
for(int i=sr; i < sr + 3; i++) {
	for(int j=sc; j < sc + 3; j++) {
		if(board[i][j] == val)
            return false;
    }
}

3×3의 위치는 9×9 사이즈에서 3개로 나누면 총 9칸이 생기는데, 각 칸의 위치는 왼쪽 위를 기준으로 할 것이기 때문에 나눗셈을 통해 나머지를 버린 뒤 다시 3을 곱하여 0, 3, 6 중 하나가 나올 수 있도록 한다.

 

(0,0) 부터 재귀호출로 순회하면서 배열의 원소가 0일경우 3가지에 대해 체크해준다.

먼저 열부터 옮기면서 재귀호출 하고 끝에 다다르면 행을 한칸 옮겨주며 재귀호출해준다.

재귀호출하면서 모든 값이 다 채워진다면 출력하고 System.exit(0)을 호출하여 끝내준다.

 

코드

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

public class Main {	 
	
	static int board[][] = new int[9][9];
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		for(int i=0;i<9;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<9;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		sudoku(0,0);
		
	}
	
	static void sudoku(int r, int c) {
		if(c == 9) {
			sudoku(r+1, 0);
			return;
		}
		if(r == 9) {
			for(int i=0;i<9;i++) {
				for(int j=0;j<9;j++) {
					System.out.print(board[i][j]+" ");
				}
				System.out.println();
			}
			
			System.exit(0);
		}
		
		if(board[r][c] == 0) {
			for(int i=1;i<=9;i++) {
				if(check(r, c, i)) {
					board[r][c] = i;
					sudoku(r, c+1);
				}
			}
			board[r][c] = 0;
			return;
		}
		
		sudoku(r, c+1);
	}
	
	static boolean check(int r, int c, int val) {
		for(int i=0;i<9;i++) {
			if(board[r][i] == val)
				return false;
		}
		
		for(int i=0;i<9;i++) {
			if(board[i][c] == val)
				return false;
		}
		
		int sr = (r/3)*3;
		int sc = (c/3)*3;
		
		for(int i=sr; i < sr + 3; i++) {
			for(int j=sc; j < sc + 3; j++) {
				if(board[i][j] == val)
					return false;
			}
		}
		
		return true;
	}
	
}