[백준] 2580: 스도쿠 (Java, Python)

스도쿠

백준 2580 백트래킹 비트마스킹 Python Java

문제 분석

• 9×9 스도쿠 판의 빈 칸(0)을 규칙에 맞게 채우기
• 행 제약: 각 가로줄에 1~9가 한 번씩
• 열 제약: 각 세로줄에 1~9가 한 번씩
• 박스 제약: 3×3 정사각형 안에 1~9가 한 번씩
• 스페셜 저지: 여러 답 중 하나만 출력하면 됨
• 시간 제한: 1초 (PyPy3: 1172ms) — Python3으로는 통과 불가, PyPy3 필요

접근법

• 백트래킹: 빈 칸 리스트를 미리 수집하고, 순서대로 가능한 숫자를 넣어보면서 탐색
• 비트마스크 최적화: 행/열/박스별 사용된 숫자를 비트로 관리하여 O(1) 체크
• row[i], col[j], box[b]: 각각 사용된 숫자의 비트마스크
• 가능한 숫자 = ~(row[i] | col[j] | box[b]) & 0x3FE (비트 1~9 범위)

핵심 비트 연산 테크닉

• avail & -avail — lowest set bit 추출 (가능한 숫자 하나씩 시도)
• bit.bit_length() - 1 — 비트 위치 → 숫자 변환
• row[i] ^= bit — 백트래킹 시 비트 해제

풀이 (Python — PyPy3 제출)

import sys
input = sys.stdin.readline

board = []
row = [0] * 9      # row[i]: i번 행에서 사용된 숫자 비트마스크
col = [0] * 9      # col[j]: j번 열에서 사용된 숫자 비트마스크
box = [0] * 9      # box[b]: b번 박스에서 사용된 숫자 비트마스크
blanks = []        # 빈 칸 좌표 리스트

for i in range(9):
    line = list(map(int, input().split()))
    board.append(line)
    for j in range(9):
        if line[j] == 0:
            blanks.append((i, j))
        else:
            bit = 1 << line[j]
            row[i] |= bit
            col[j] |= bit
            box[(i // 3) * 3 + j // 3] |= bit

def solve(idx):
    if idx == len(blanks):
        return True                     # 모든 빈 칸 채움 → 성공
    i, j = blanks[idx]
    b = (i // 3) * 3 + j // 3
    avail = ~(row[i] | col[j] | box[b]) & 0x3FE  # 가능한 숫자 비트
    while avail:
        bit = avail & -avail            # lowest set bit
        num = bit.bit_length() - 1      # 비트 → 숫자
        board[i][j] = num
        row[i] |= bit; col[j] |= bit; box[b] |= bit
        if solve(idx + 1):
            return True
        row[i] ^= bit; col[j] ^= bit; box[b] ^= bit  # 백트래킹
        avail ^= bit
    board[i][j] = 0
    return False

solve(0)
for line in board:
    print(' '.join(map(str, line)))

풀이 (Java)

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

public class Main {
    static int[][] board = new int[9][9];
    static int[] row = new int[9], col = new int[9], box = new int[9];
    static int[][] blanks;
    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 0) {
                    list.add(new int[]{i, j});
                } else {
                    int bit = 1 << board[i][j];
                    row[i] |= bit;
                    col[j] |= bit;
                    box[i / 3 * 3 + j / 3] |= bit;
                }
            }
        }
        cnt = list.size();
        blanks = list.toArray(new int[0][]);
        solve(0);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (j > 0) sb.append(' ');
                sb.append(board[i][j]);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    static boolean solve(int idx) {
        if (idx == cnt) return true;
        int i = blanks[idx][0], j = blanks[idx][1];
        int b = i / 3 * 3 + j / 3;
        int avail = ~(row[i] | col[j] | box[b]) & 0x3FE;
        while (avail != 0) {
            int bit = avail & -avail;
            int num = Integer.numberOfTrailingZeros(bit);
            board[i][j] = num;
            row[i] |= bit; col[j] |= bit; box[b] |= bit;
            if (solve(idx + 1)) return true;
            row[i] ^= bit; col[j] ^= bit; box[b] ^= bit;
            avail ^= bit;
        }
        board[i][j] = 0;
        return false;
    }
}

예제 트레이스

빈 칸: (0,0), (1,4), (1,7), (2,0), (2,2), ...

(0,0) 탐색:
  row[0] = {3,5,4,6,9,2,7,8}  → 비트: 0b1111101100
  col[0] = {7,3,8,5,9,6,2}    → 비트: 0b1111101100
  box[0] = {3,5,7,8,2,6}      → 비트: 0b0111101100
  avail = ~(row|col|box) & 0x3FE
        = 0b0000000010 → {1}만 가능
  board[0][0] = 1 ✓

(1,4) 탐색:
  row[1] = {7,8,2,1,5,6,9}    → {3,4} 가능
  col[4] = {6,7,4,1,2,5,9}    → {3,8} 가능
  box[1] = {4,6,9,1,5,2,8}    → {3,7} 가능
  교집합 = {3}
  board[1][4] = 3 ✓

... 각 빈 칸마다 비트 연산으로 가능한 숫자를 즉시 계산
    가능한 숫자가 없으면 백트래킹

시간 복잡도

O(9^K)

K = 빈 칸 수, 실제로는 pruning으로 매우 빠름

공간 복잡도

O(81)

보드 + 비트마스크 배열

클린 코드 — Python

import sys
input = sys.stdin.readline
board = []
row = [0]*9; col = [0]*9; box = [0]*9; blanks = []
for i in range(9):
    line = list(map(int, input().split()))
    board.append(line)
    for j in range(9):
        if line[j] == 0: blanks.append((i, j))
        else:
            bit = 1 << line[j]
            row[i] |= bit; col[j] |= bit; box[(i//3)*3+j//3] |= bit
def solve(idx):
    if idx == len(blanks): return True
    i, j = blanks[idx]; b = (i//3)*3+j//3
    avail = ~(row[i]|col[j]|box[b]) & 0x3FE
    while avail:
        bit = avail & -avail; num = bit.bit_length()-1
        board[i][j] = num
        row[i] |= bit; col[j] |= bit; box[b] |= bit
        if solve(idx+1): return True
        row[i] ^= bit; col[j] ^= bit; box[b] ^= bit
        avail ^= bit
    board[i][j] = 0; return False
solve(0)
for line in board: print(' '.join(map(str, line)))

클린 코드 — Java

import java.io.*;
import java.util.*;
public class Main {
    static int[][] board = new int[9][9];
    static int[] row = new int[9], col = new int[9], box = new int[9];
    static int[][] blanks; static int cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 0) list.add(new int[]{i, j});
                else { int bit = 1<<board[i][j]; row[i]|=bit; col[j]|=bit; box[i/3*3+j/3]|=bit; }
            }
        }
        cnt = list.size(); blanks = list.toArray(new int[0][]);
        solve(0);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) { if (j>0) sb.append(' '); sb.append(board[i][j]); }
            sb.append('\n');
        }
        System.out.print(sb);
    }
    static boolean solve(int idx) {
        if (idx == cnt) return true;
        int i = blanks[idx][0], j = blanks[idx][1], b = i/3*3+j/3;
        int avail = ~(row[i]|col[j]|box[b]) & 0x3FE;
        while (avail != 0) {
            int bit = avail & -avail, num = Integer.numberOfTrailingZeros(bit);
            board[i][j] = num; row[i]|=bit; col[j]|=bit; box[b]|=bit;
            if (solve(idx+1)) return true;
            row[i]^=bit; col[j]^=bit; box[b]^=bit; avail^=bit;
        }
        board[i][j] = 0; return false;
    }
}