[백준] 2580번: 스도쿠

문제

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

우리가 흔히 알고 있는 스도쿠다
사용자가 입력하는 것은 9x9 형태

0으로 입력받은 칸에 맞는 숫자를 넣어주면 되는 문제다

알고리즘

간단해보이지만.. 생각보다 신경써야 할 것들이 많은 그런 문제

신경써야 할 부분은 세가지
1. 빈칸이 위치한 가로줄에 없는 숫자인가
2. 빈칸이 위치한 세로줄에 없는 숫자인가
3. 빈칸이 위치한 3x3 형태의 정사각형에 없는 숫자인가

3번은 조금 더 생각을 해야 하는데 맨 위, 왼쪽 칸의 좌표를 (0,0)이라고 하자

0~2 / 3~5 / 6~8 칸이 하나의 정사각형에 같이 위치한다
즉 이 숫자들을 묶는 경우가 필요한데 이는 나누기를 통해 계산할 수 있다

(x / 3) * 3을 해주면
0, 1, 2는 0이라는 값에
3, 4, 5는 1
6, 7, 8은 2 라는 결과값이 나오게 된다

다시 정리를 해보자
1의 경우

for (int i=0 ; i<9 ; i++) {
	if (arr[row][i] == value)
    	return false;
        
return true;

2의 경우

for (int i=0 ; i<9 ; i++) {
	if (arr[i][col] == value)
    	return false;
        
return true;

3의 경우

in_row = (row/3) * 3
in_col = (col/3) * 3
for (int i=in_row ; i<in_row + 3 ; i++) {
	for (int j=in_col ; j<in_col + 3 ; j++) {
    	if (arr[i][j] == value)
        	return false;
    }
}

return true;

이 코드들을 기반으로 하나씩 차근차근 시작해보자

코드

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

public class Baekjoon2580 {
	
	static int[][] board = new int[9][9];
	
	public static boolean find(int row, int col, int value) {
		
		// 같은 가로줄에 있는 수 중 겹치는 수가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (board[row][i] == value) {
				return false;
			}
		}
	    
		// 같은 세로줄에 있는 수 중 겹치는 수가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (board[i][col] == value) {
				return false;
			}
		}
	 
		// 3x3 형태의 정사각형에 없는지 검사
		int in_row = (row / 3) * 3;
		int in_col = (col / 3) * 3;
	 
		for (int i = in_row; i < in_row + 3; i++) {
			for (int j = in_col; j < in_col + 3; j++) {
				if (board[i][j] == value) {
					return false;
				}
			}
		}
	
		// 중복되는 것이 없을 경우 true 반환
		return true;
	}
	
	// 숫자를 채우는 함수 sudoku
	public static void sudoku(int row, int col) {
		// 만약 이미 가로줄이 다 찼으면 세로줄은 다 찼는지 확인
		if (row == 9) {
			sudoku(0, col+1);
			return;
		}
		
		// 가로줄도 다 차고 세로줄도 다 찼으면 각 칸에 해당하는 문자 출력
		if (col == 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);
		}
		
		// 만약 해당 칸이 비어있으면 find 함수를 사용해서 어떤 숫자가 들어갈 수 있는지 확인
		if (board[row][col] == 0) {
			for (int i=1 ; i<=9 ; i++) {
				if (find(row, col, i) == true) {
					board[row][col] = i;
					// 다음 칸에 해당하는 숫자 찾기
					sudoku(row+1, col);
				}
			}
			// 만약 i에 들어갈 숫자가 이미 다른 칸에 있었다면 i를 집어 넣지 않고 다시 0으로 초기화
			board[row][col] = 0;
			return;
		}
		
		// 다음 칸 채우기 실행
		sudoku(row+1, col);
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 숫자 입력
		for (int i=0 ; i<9 ; i++) {
			String[] input = br.readLine().split(" ");
			for (int j=0 ; j<9 ; j++) {
				board[i][j] = Integer.parseInt(input[j]);
			}
		}
		
		sudoku(0,0);
	}
}

마무리

으 역시나 이번 문제도 재귀함수다
사람이 스도쿠를 풀 때와는 다르게 컴퓨터는 하나씩 진행하고 가능한 문자들을 다 저장해놓고 하나씩 확인해야 한다
아무래도 컴퓨터가 처리하는 방식에 조금 더 익숙해지면 풀기 쉽겠다