2580번 문제

문제

풀이

후하 ^^.. 풀고나니 쾌감이 장난 아닌 문제

접근 방식

백트래킹을 이용해서 풀었다.

1. 모든 자리를 순회하며 비어있는 자리 [a][b]를 찾는다.
2. [a][b] 자리에 들어갈 수 있는 수를 골라낸다.
   2-1. 같은 행과 같은 열을 체크하여 이미 존재하는 수 체크
   2-2. 같은 정사각형 범위를 체크하여 이미 존재하는 수 체크
3. 들어갈 수 있는 수가 존재할 경우, [a][b] 에 해당 수를 지정하고, 다음 비어있는 자리를 찾아간다.
4. 들어갈 수 있는 수가 존재하지 않을 경우, 이전 자리로 돌아가 다른 수를 지정하도록 한다.
5. 더이상 비어있는 자리가 없을 경우, 현재의 스도쿠 상태를 출력한다.

제출 코드

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

public class Main {
    static int[][] matrix;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        matrix = new int[9][9];
        int last = 0;
        for(int i=0; i<9; i++) {
            st = new StringTokenizer(br.readLine()); 
            for(int j=0; j<9; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
                if(matrix[i][j]==0) last++;
            }
        }
        sudoku(last);
        System.out.println(sb);
    }

    public static boolean sudoku(int last) {
        if(last == 0) { // 더 이상 빈자리가 없는 경우 스도쿠 출력
            for(int i=0; i<9; i++) {
                for(int j=0; j<9; j++) {
                    sb.append(matrix[i][j]).append(' ');
                }
                sb.append('\n');
            }
            return true;
        }

        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                if(matrix[i][j]==0) { // 빈 자리 [i][j] 찾기
                    int bit1 = checkRowAndCol(i, j); 
                    int bit2 = checkSquare(i,j);
                    int bit = bit1 | bit2;

                    for(int pos=1; pos<=9; pos++) {
                        if(((bit >> pos) & 1) == 0) { // [i][j]에 넣을 수 있는 수 = pos 찾기
                            matrix[i][j] = pos; 
                            if(sudoku(last-1)) { // [i][j] = pos 넣고, 다음 빈 자리로
                                return true; 
                            }
                            matrix[i][j] = 0; // 만일 도중에 실패한다면, 다시 [i][j] = 0 처리
                        }
                    }
                    if(matrix[i][j]==0) return false; // [i][j]에 넣을 수 있는 수가 없다면, 실패 처리
                }
            }
        }
        return false;
    }

    public static int checkRowAndCol(int row, int col) {
        // 가로 세로 범위 체크
        int bit = 0;
        for(int i=0; i<9; i++) {
            if(matrix[row][i]!=0) {
                bit = bit | (1 << matrix[row][i]);
            }
            if(matrix[i][col]!=0) {
                bit = bit |  (1 << matrix[i][col]);
            }
        }
        return bit;
    }

    public static int checkSquare(int row, int col) {
        // 정사각형 범위 체크
        int bit = 0;
        for(int i=(row/3)*3; i/3 == row/3; i++) {
            for(int j=(col/3)*3; j/3 == col/3; j++) {
                if(matrix[i][j]!=0) {
                    bit = bit | (1 << matrix[i][j]);
                }
            }
        }
        return bit;
    }
}

설명

[a][b] 자리에 들어갈 수 있는 번호를 골라내는 과정에서 비트마스킹을 사용했다.

• int checkRowAndCol(int row, int col) : matrix[a][b]와 같은 행과 열을 확인하여 이미 존재하는 번호의 위치에 비트 1을 설정한다.
• int checkSquare(int row, int col) : matrix[a][b]와 같은 정사각형 내에 이미 존재하는 번호의 위치에 비트 1을 설정한다.

두 메서드가 반환하는 정수를 OR 연산하면 두 범위 중 하나라도 존재할 경우, 해당하는 위치의 비트가 1이 된다.
따라서 1~9의 범위 중 비트가 0인 위치 pos가 [a][b]위치에 들어갈 수 있는 번호가 된다.

---

다른 사람들은 어떻게 풀었을지 궁금하다 .. 찾아보러 가야지