백준 2580번 : 스도쿠 java

이 문제는 스도쿠 문제를 백트래킹을 이용하여 푸는 문제입니다.

위와 같은 스도쿠 판이 있다고 가정하겠습니다.

이 스도쿠 판에서 빈칸들을 채우기 위해서는 아래와 같이 가로, 세로, 박스 안을 확인해야 합니다.

이 세 영역에 빈칸에 넣는 수와 같은 수가 존재하지 않아야 빈칸에 수를 삽입할 수 있습니다.

코드를 보면서 이 문제의 풀이에 대해 더 자세히 설명드리도록 하겠습니다.

---

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

public class Main {
    static int[][] board;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        board = new int[9][9];

        for(int i = 0; i<9; i++){
            StringTokenizer 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 row, int col){
        if(col == 9){
            sudoku(row+1, 0);
            return;
        }

        if(row == 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[row][col] == 0){
            for(int i = 1; i<=9; i++){
                if(check(row, col, i)){
                    board[row][col] = i;
                    sudoku(row, col + 1);
                }
            }
            board[row][col] = 0;
            return;
        }

        sudoku(row, col+1);
    }

    static boolean check(int row, int col, int val){
        //가로 방향 탐색
        for(int i = 0; i<9; i++){
            if(board[row][i] == val)
                return false;
        }
        //세로 방향 탐색
        for(int i = 0; i<9; i++){
            if(board[i][col] == val)
                return false;
        }
        //3x3 박스 안 탐색
        int rowStart = (row/3)*3;
        int colStart = (col/3)*3;

        for(int i = rowStart; i<rowStart+3; i++){
            for(int j = colStart; j<colStart+3; j++)
                if(board[i][j] == val)
                    return false;
        }

        return true;
    }
}

우선 위에서 설명드린 빈칸에 수가 들어갈 수 있는지를 확인하는 check 함수를 만들었습니다.

그리고 한 칸씩 진행하면서 스도쿠를 채우는 sudoku 함수도 만들었습니다.

이 문제에서 집중해서 보셔야 하는 곳은 아래의 코드 부분입니다.

if(board[row][col] == 0){
    for(int i = 1; i<=9; i++){
        if(check(row, col, i)){
            board[row][col] = i;
            sudoku(row, col + 1);
        }
    }
    board[row][col] = 0;
    return;
}

sudoku(row, col+1);

스도쿠 칸이 비었을 때 앞에서부터 스도쿠 칸을 채우기 시작하면 뒤에서 빈칸이 있음에도 불구하고 가로, 세로, 박스 안에 같은 수가 존재하여 칸을 채울 수 없는 상황이 발생합니다.

따라서 이를 해결하기 위해서 1~9를 check 함수를 이용하여 순회했음에도 board[row][col]이 0으로 남아있다면 return 하게 만들어서 이전 칸에 다른 수를 넣게 만드는 백트래킹 기법을 이용하였습니다.