[BOJ-2239][백트래킹] 스도쿠 - Java

문제 바로가기

2239번: 스도쿠

 

와 스도쿠 문제입니다. 예전에 진짜 많이 했는데

n-Queen 이랑 궤를 같이 한다고 생각합니다. 둘 수 있는 애 두다가 안되면 백트래킹..

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

public class Main {
    static class Dir{
        int y, x;
        Dir(int y, int x){
            this.y = y; this.x = x;
        }
    }

    static int[][] board = new int[9][9];
    static int zero;

    public static void main(String[] args) throws IOException {
        input();

        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] != 0) continue;
                dfs(new Dir(i, j));
            }
        }

    }

    public static void printBoard() {
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }

    public static void dfs(Dir cur) {

        for(int i = 1; i <= 9; i++) {
            if(check(cur, i)) {
                board[cur.y][cur.x] = i;
                zero--;

                if(zero == 0) {
                    printBoard();

                    System.exit(0);;
                }

                outer:
                for(int k = 0; k < 9; k++) {
                    for(int j = 0; j < 9; j++) {
                        if(board[k][j] != 0) continue;
                        dfs(new Dir(k, j));
                        break outer;
                    }
                }

                board[cur.y][cur.x] = 0;
                zero++;
            }
        }

        return;
    }


    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i = 0; i < 9; i++) {
            String temp = br.readLine();
            for(int j = 0; j < 9; j++) {
                board[i][j] = temp.charAt(j) - '0';
                if(board[i][j] == 0) zero++;
            }
        }

    }

    public static boolean check(Dir cur, int num) {
        // 행
        for(int i = 0; i < 9; i++) {
            if(board[cur.y][i] == num) return false;
        }

        // 열
        for(int i = 0; i < 9; i++) {
            if(board[i][cur.x] == num) return false;
        }

        // 사각형
        int sy = (cur.y / 3) * 3;
        int sx = (cur.x / 3) * 3;    

        for(int i = sy; i < sy + 3; i++) {
            for(int j = sx; j < sx + 3; j++) {
                if(board[i][j] == num) return false;
            }
        }

        return true;
    }
}

종료 조건을 위해 맨 처음 입력받을 때 0의 개수를 구해놨습니다. zero의 값이 0이 됐을 때가 스도쿠가 완성된 첫번째 경우니까 이때 출력하고 바로 냉큼 프로그램을 종료해줬습니다.

 

배열을 돌면서 빈 칸일 때 DFS로 들어가는 식으로 하면 됩니다.

사실 백트래킹 자체는 어려운 부분은 없져. 어쩌면 행, 열, 3x3 네모안을 체크하는 부분이 젤 까다로울 수도 있게씀다.

행, 열은 간단하고 네모박스 체크하는 부분은 그렇게 생각해씀니다. 그 뭐냐

작은 네모가 총 3x3 개가 있져. 각각 (0, 0) (0, 1) (0, 2) 이런 식으로 좌표를 생각할 수 있겠죠. 얘는 그럼 원래 좌표를 각각 3으로 나눈 몫이 됩니다. 거기에 원래는 세배 크기니깐 다시 *3을 해서 간단하게 네모 박스를 구했습니다.

 

감사합니다!!