[백준 2239] 스도쿠 - JAVA

문제 링크 : https://www.acmicpc.net/problem/2239

코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!

---

문제 정의

• 9×9 크기의 보드가 있을 때 각각의 칸에는 1 ~ 9 까지의 숫자가 배치
• 같은 행, 열, 3 x 3 영역에는 자신과 같은 숫자가 없어야 한다.
• 9개의 줄에 9개의 숫자로 보드가 입력된다.
• 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.
• 9개의 줄에 9개의 숫자로 답을 출력한다.
• 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력

---

접근 방법

1. 스도쿠를 이중 for문으로 순회하며 현재 빈 칸을 찾는다.
2. 현재 빈칸에 1~9까지 숫자 중 가능한 숫자를 넣고 재귀한다.
   2-1. 모든 숫자를 대입해도 넣을 수 없는 경우 false를 반환
3. 가장 먼저 스도쿠의 끝에 도달한 완성된 스도쿠를 출력

스도쿠 조건 확인 로직

스도쿠는 세 가지 조건을 충족해야 합니다.

• 해당 열에 같은 숫자가 존재하면 안된다
• 해당 행에 같은 숫자가 존재하면 안된다.
• 해당 서브 보드에 같은 숫자가 존재하면 안된다.

그래서 이 세 가지 여부를 판별할 수 있는
row col subBoard 2차원 배열을 선언했습니다.

위 3가지 조건을 판별해 충족하는 숫자에 대해
값을 대입하고 백트래킹을 수행합니다.

---

출력 로직

if (y == 9) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            sb.append(board[i][j]);
        }
        sb.append("\n");
    }
    return true;
}

가장 먼저 스도쿠를 채운 백트래킹에 대해
정답을 출력하고 true를 반환하게 됩니다.

---

예시

간단하게 하나의 빈 스도쿠의 대입 가능한 숫자를 찾는 예시를 들겠습니다.

왼쪽의 스도쿠를 채우는 과정에서 (0, 1)에 존재하는 빈 곳에 대입 가능한 숫자를 찾아보겠습니다.

• Row[0]을 탐색: 2 4 6 7 8 탐색 가능
• Col[1]을 탐색: 1 2 3 4 5 7 8 9의 숫자를 탐색 가능
• subBoard[0]을 탐색: 4 5 6 7 8 9의 숫자를 탐색 가능

이 세 조건의 교집합은
4 7 8 이며 해당 숫자들이 대입 가능한 숫자들이 됩니다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static boolean[][] row = new boolean[9][10];
    static boolean[][] col = new boolean[9][10];
    static boolean[][] subBoard = new boolean[9][10];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] board = new int[9][9];

        for (int i = 0; i < 9; i++) {
            String numbers = br.readLine();
            for (int j = 0; j < 9; j++) {
                board[i][j] = Integer.parseInt(String.valueOf(numbers.charAt(j)));
                if (board[i][j] != 0) {
                    row[i][board[i][j]] = true;
                    col[j][board[i][j]] = true;
                    subBoard[((i/3)*3+(j/3))][board[i][j]] = true;
                }
            }
        }
        bt(0, 0, board);
        System.out.println(sb);
    }


    static boolean bt(int y, int x, int[][] board) {
        if (y == 9) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(board[i][j]);
                }
                sb.append("\n");
            }
            return true;
        }

        int ny = x + 1 == 9 ? y + 1 : y;
        int nx = x + 1 == 9 ? 0 : x + 1;

        if (board[y][x] == 0) {
            for (int k = 1; k <= 9; k++) {
                if (!row[y][k] && !col[x][k] && !subBoard[((y/3)*3+(x/3))][k]) {
                    row[y][k] = true;
                    col[x][k] = true;
                    subBoard[((y/3)*3+(x/3))][k] = true;
                    board[y][x] = k;

                    if (bt(ny, nx, board)) return true;

                    row[y][k] = false;
                    col[x][k] = false;
                    subBoard[((y/3)*3+(x/3))][k] = false;
                    board[y][x] = 0;

                }
            }
        }
        else {
            if (bt(ny, nx, board)) return true;
        }
        return false;
    }
}