[BOJ] 2239번. 스도쿠 - JAVA

🧷 문제 링크

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

2239번: 스도쿠

 

📄 풀이 과정

문제 유형 : 백트랙킹, 구현

 

이 문제는 숫자가 행과 열과 3*3 크기의 사각형 안에 이미 쓰여졌는지를 어떻게 판별하느냐에 따라 풀 수 있는 방법이 다양하다.

① 정석대로 체크해야할 세 가지 영역을 for 반복문을 돌면서 넣고자 하는 숫자가 쓰여졌는지를 체크한다.

② HashSet을 사용한다.

③ 비트마스킹을 이용한다.

 

나는 'HashSet으로 한게 700ms, bit연산을 이용한게 192ms 정도 나왔다. 메모리 또한 bit 연산을 이용한 체크방식이 10배이상 작게든다.' 라는 블로그의 말에 비트마스킹을 이용해 풀었다.

(참고: https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-2239-%EC%9E%90%EB%B0%94-%EC%8A%A4%EB%8F%84%EC%BF%A0-BOJ-2239-JAVA)

 

 

1. 입력으로 주어진 숫자를 받으면서 0이라면 list에 (r, c, gridNum)을 넣어준다. (for문으로 탐색하며 0을 찾을 수도 있지만 list 를 사용하는게 시간을 절약할 수 있다.)

 

2. 0이 아닌 숫자라면 체크를 해야 한다.

- chk[0] 에는 각각 행에 쓰여진 숫자를 체크한다.

- chk[1] 에는 각각 열에 쓰여진 숫자를 체크한다.

- chk[2] 에는 3*3 크기의 사각형에 쓰여진 숫자를 체크한다.

 

이때 비트마스킹을 사용한다면 chk[0][r] |= (1<<num) 로 체크할 수 있다. ( | 연산자는 양쪽의 두 숫자를 2진법으로 나타낸 후, 각 칸을 비교해 둘 중 하나라도 1이 있다면 1로, 아니라면 0으로 나타내기 때문에 1을 num 번 왼쪽으로 이동했을 때의 칸을 chk[0][r] 에 1로 바꿔 그 숫자가 사용됐음을 표시한다.)

 

3. 각각의 빈칸에 1~9 를 대입해보면서 (1부터 대입해본다면 사전순으로 출력하라는 조건도 만족시킬 수 있다.) 현재 빈칸에 현재 숫자를 대입할 수 있는지 체크하고 없다면 continue 로 다음 숫자, 대입할 수 있다면 대입한 후 다음 빈칸으로 넘어간다.

 

체크여부는 chk[0][r] & 1<<num 로 확인할 수 있다. | 과 마찬가지로 양쪽의 두 숫자를 2진법으로 나타낸 후, 각 칸을 비교하는데, & 연산자는 둘 다 1이여야만 1이다. 따라서 chk[0][r] 가 0 이고 1<<num 이 1이라면 0 을 출력함으로써 사용하지 않은 숫자이지만 0이 아니라면 이미 사용된 숫자이다. 

 

4. 모든 빈칸을 돌았다면 해당 숫자들을 출력한다.

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Main_bj_2239_스도쿠 {
    
    static class Point{
        int r, c, gridNum;
 
        public Point(int r, int c, int gridNum) {
            super();
            this.r = r;
            this.c = c;
            this.gridNum = gridNum;
        }
    }
    
    static int[][] ans, chk;
    static LinkedList<Point> zerolist;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input_bj_2239.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ans = new int[9][9];
        chk = new int[3][9];        // [0]: 각 행의 숫자 체크 [1]: 각 열에 숫자 체크, [2]: 3*3 에 숫자 체크
        zerolist = new LinkedList<>();
        
        for(int i=0; i<9; i++) {
            String s = br.readLine();
            for(int j=0; j<9; j++) {
                ans[i][j] = s.charAt(j) - '0';
                int gridNum = i/3*3+j/3;
                
                if(ans[i][j]==0) {
                    zerolist.offer(new Point(i, j, gridNum));
                    continue;
                }
                
                // 체크
                chk[0][i] |= 1<<ans[i][j];
                chk[1][j] |= 1<<ans[i][j];
                chk[2][gridNum] |= 1<<ans[i][j];
            }
        }
        
        go(0);    // 첫 번째 빈칸부터 채우기 시작함
        System.out.print(sb.toString());
        br.close();
    }
    
    static boolean go(int idx) {
        if(idx == zerolist.size()) {    // 모든 빈칸을 채움
            
            for(int i=0; i<9; i++) {
                for(int j=0; j<9; j++) {
                    sb.append(ans[i][j]);
                }
                sb.append("\n");
            }
            return true;
        }
        
        Point p = zerolist.get(idx);
        int r = p.r; int c = p.c; int gridNum = p.gridNum;
        
        for(int num=1; num<=9; num++) {
            if((chk[0][r] & 1<<num) !=0 || (chk[1][c] & 1<<num) !=0 || 
                    (chk[2][gridNum] & 1<<num) !=0) continue;            // 이미 있는 숫자
            
            ans[r][c] = num;
            chk[0][r] |= 1<<num;     // 현재 숫자 체크 표시
            chk[1][c] |= 1<<num;
            chk[2][gridNum] |= 1<<num; 
            
            if(go(idx+1)) return true;     // 다음 빈칸 채우러
            
            chk[0][r] &= ~(1<<num);     // 원상복구
            chk[1][c] &= ~(1<<num); 
            chk[2][gridNum] &= ~(1<<num); 
        }
        
        return false;
    }
    
 
}
 

 

📌 채점 결과