[SWEA | Java] 1974번 스도쿠 검증

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Psz16AYEDFAUq

SW Expert Academy

티어

소요 시간

23분

분류

브루트포스

비트마스크

코드

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int test = 1; test <= t; test++) {
            int[][] sudoku = new int[9][9];

            for (int i = 0; i < 9; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < 9; j++) {
                    sudoku[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            System.out.println("#" + test + " " + checkSudoku(sudoku));
        }
    }

    private static int checkSudoku(int[][] sudoku) {
        if (!validateGroup(sudoku)) return 0;
        if (!validateLine(sudoku)) return 0;
        return 1;
    }

    private static boolean validateLine(int[][] sudoku) {
        for (int i = 0; i < 9; i++) {
            int checkHorizontal = 0;
            int checkVertical = 0;
            for (int j = 0; j < 9; j++) {
                if ((checkHorizontal & (1 << sudoku[i][j])) != 0) return false;
                if ((checkVertical & (1 << sudoku[j][i])) != 0) return false;
                checkHorizontal |= (1 << sudoku[i][j]);
                checkVertical |= (1 << sudoku[j][i]);
            }
        }
        return true;
    }

    private static boolean validateGroup(int[][] sudoku) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int checkNumber = 0;
                for (int k = i * 3; k < i * 3 + 3; k++) {
                    for (int l = j * 3; l < j * 3 + 3; l++) {
                        if ((checkNumber & (1 << sudoku[k][l])) != 0) return false;
                        checkNumber |= (1 << sudoku[k][l]);
                    }
                }
            }
        }
        return true;
    }
}

코드 설명

스도쿠를 검증할 때 검증할 요소는 총 세 가지가 있다.

 

1️⃣ 3 x 3 블럭 검증

2️⃣ 가로 검증

3️⃣ 세로 검증

 

1️⃣번을 검증하는 함수는 validateGroup 함수이고,

2️⃣, 3️⃣번을 검증하는 함수는 validateLine 함수이다.

 

각각의 검증 함수에서 어떤 위치를 검증할 것인지는 인덱스에 달려있고, 어떻게 검증할지는 여러 가지 방법이 있을텐데 위의 코드에서는 비트마스크를 이용했다.

성능적으로 그렇게 뛰어날 것 같지는 않지만 비트마스크가 편하고 코드가 간단하다.

 

validateLine 함수만 살펴보도록 하자.

private static boolean validateLine(int[][] sudoku) {
    for (int i = 0; i < 9; i++) {
        int checkHorizontal = 0;
        int checkVertical = 0;
        for (int j = 0; j < 9; j++) {
            if ((checkHorizontal & (1 << sudoku[i][j])) != 0) return false;
            if ((checkVertical & (1 << sudoku[j][i])) != 0) return false;
            checkHorizontal |= (1 << sudoku[i][j]);
            checkVertical |= (1 << sudoku[j][i]);
        }
    }
    return true;
}

 

checkHorizontal : 가로 선 검증 변수

checkVertical : 세로 선 검증 변수

 

만약 첫 숫자가 7이라면 checkHorizontal(혹은 checkVertical)에 (1 << 7) 즉, 128이라는 숫자를 저장하게 된다.

다음 숫자로 다시 7이 나오게 된다면 1 << 7과 경합해보았을 때 0이 아닌 128이라는 값이 나오게 되므로 중복된 숫자가 존재해 스도쿠 규칙이 지켜지지 않음을 알 수 있다.

 

비트마스크를 사용하면 항상 실수하는 부분이 있는데 0이 아닌 것을 검증해야하는데 자꾸 1일 때로 비교한다는 것이다.

이번 문제도 풀기는 되게 빨리 풀어놓고 왜 안되지 하면서 계속 디버깅하느라 시간이 늦어졌다.