[백준 2239번] 스도쿠

문제 링크: 2239번 스도쿠

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

 

empty는 채워지지 않은 칸의 인덱스들을 저장하고 있고, fill은 empty의 emptyId번째 칸을 채우는 함수이다. 즉, emptyId == empty.size()라는 조건은 empty의 모든 칸들을 다 채웠다는 것을 의미하므로, 그 때 스도쿠 퍼즐을 출력하면 된다.

 

51번째 라인의 존재 의의는 무엇일까?

 

'지금의 상태'가 '불가능한 상태'인 것에는 두 가지 경우가 있다.

첫째는, candis의 크기가 0인 것이다.

둘째는, fill()내의 for문을 다 돈 경우이다.

두 번째 경우를 고려해서, 이 때에는 값을 초기화해놓고 전 상태로 돌아가야 한다.

 

그렇지 않으면, emptyId가 자신보다 큰 empty의 영향을 받아 (원래는 자기 뒤의 empty는 채우지 않았다고 가정해야 함) candis가 잘못 구해질 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Pos {
    int row;
    int col;

    Pos(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {
    static int[][] board = new int[9][9];
    static List<Pos> empty = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 9; i++) {
            String line = br.readLine();
            for (int j = 0; j < 9; j++) {
                board[i][j] = line.charAt(j) - '0';
                if (board[i][j] == 0) {
                    empty.add(new Pos(i, j));
                }
            }
        }

        fill(0);
    }

    static void fill(int emptyId) {
        if (emptyId == empty.size()) {
            print();
            System.exit(0);
        }

        Pos cur = empty.get(emptyId);
        List<Integer> candis = candi(cur);

        for (int item : candis) {
            board[cur.row][cur.col] = item;
            fill(emptyId + 1);
        }

        board[cur.row][cur.col] = 0;
    }

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

    static List<Integer> candi(Pos p) {
        boolean[] possible = new boolean[10]; Arrays.fill(possible, true);

        // horizontal
        for (int i = 0; i < 9; i++) {
            possible[board[p.row][i]] = false;
        }

        // vertical
        for (int i = 0; i < 9; i++) {
            possible[board[i][p.col]] = false;
        }

        // square
        int r = (p.row / 3) * 3;
        int c = (p.col / 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                possible[board[r+i][c+j]] = false;
            }
        }

        List<Integer> candi = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            if (possible[i]) {
                candi.add(i);
            }
        }
        return candi;
    }
}