[Gold IV] 스도쿠 - 2239

문제 링크

성능 요약

메모리: 16872 KB, 시간: 336 ms

분류

백트래킹, 구현

제출 일자

2024년 9월 4일 03:56:00

문제 설명

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

문제 풀이

비트마스킹으로 세로, 가로, 3x3 격자를 체크한다.
재귀적으로 진행하며 조건 만족시 체크 및 재귀호출 후 다시 되돌리는 백트래킹 작업 필요.

코드

/**
 * Author : nowalex322, Kim hyeonjae
 */

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

/**
 * 비트마스킹 연습
 */
public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder sb = new StringBuilder();
	static int map[][], checkRow[], checkCol[], check3by3[][];
    static List<int[]> listToSolve = new ArrayList<>();
    private static boolean solved = false;
    public static void main(String[] args) throws IOException {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        map = new int[10][10];
        checkRow = new int[10];
        checkCol = new int[10];
        check3by3 = new int[4][4];

        for (int i=1; i<=9; i++) {
            String s = br.readLine();
            for (int j=1; j<=9; j++) {
                int num = s.charAt(j-1) - '0';
                checkRow[i] |= 1 << num;
                checkCol[j] |= 1 << num;
                check3by3[((i-1)/3)+1][((j-1)/3)+1] |= 1 << num;
                map[i][j] = num;
                if (num == 0) {
                	listToSolve.add(new int[]{i, j});
                }
            }
        }

        sudoku(0);

        br.close();
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void sudoku(int idx) {
        if (solved) return;
        
        if (idx == (listToSolve.size())) {
            for (int i=1; i<=9; i++) {
                for (int j=1; j<=9; j++) {
                    sb.append(map[i][j]);
                }
                sb.append("\n");
            }
            solved = true;
            return;
        }

        int[] zero = listToSolve.get(idx);
        int r = zero[0];
        int c = zero[1];
        for (int i=1; i<=9; i++) {
            if (((checkRow[r] & 1<<i) == 0) && ((checkCol[c] & 1<<i) == 0) && ((check3by3[((r-1)/3)+1][((c-1)/3)+1] & 1<<i) == 0)) {
                map[r][c] = i;
                checkRow[r] |= 1 << i;
                checkCol[c] |= 1 << i;
                check3by3[((r - 1) / 3) + 1][((c - 1) / 3) + 1] |= 1 << i;
                sudoku(idx + 1);
                
                map[r][c] = 0;
                checkRow[r] &= ~(1 << i);
                checkCol[c] &= ~(1 << i);
                check3by3[((r - 1) / 3) + 1][((c - 1) / 3) + 1] &= ~(1 << i);
            }
        }
    }
}