[백준 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;
​​​​}
}