[JAVA]백준 2580번: 스도쿠

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

2580번: 스도쿠

1. 문제 설명

 

스도쿠가 주어졌을 때 빈칸 (0)을 채우는 문제.

 

스도쿠 판을 채우는 방법이 여럿인 경우 그중 하나만 출력

 

 

2. 풀이

 

백트래킹 + 비트 연산으로 풀었다.

 

스도쿠 규칙 상 1 ~ 9까지의 숫자가 겹치지 않게 가로줄, 세로줄, 3*3 정사각형 안에 하나씩 존재해야 한다.

 

입력 값이 0인 경우에는 list에 저장하였고, 0이 아닌 경우에는 row, column, box (3*3 정사각형) 배열을 만들어 비트를 저장했다.

 

스도쿠를 만들 때는 값이 0인 자리에 1 ~ 9 사이의 값 idx가 들어간다고 했을 때 row, column, box 배열에 idx 값이 없는지 확인 후 , 없는 경우에만 idx 값을 저장하고 다음 연산을 수행했다.

 

스도쿠를 완성하면 출력하고 System.exit(0)을 하였는데, 이는 문제에서 스도쿠를 하나만 출력하라고 했기 때문이다.

 

이외에도 sudoku를 만드는 함수가 boolean 값을 return 하게 하여 return 값으로 스도쿠를 이미 출력했는지 안 했는지 확인하고 처리할 수도 있긴 하다.

 

이 처리를 안 해주게 된다면 만들 수 있는 스도쿠가 모두 출력되고 에러가 발생할 것이다. (이 처리를 안 해주면 모두 0으로만 입력값을 주었을 때 많은 스도쿠들이 출력된다..!)

 

 

 

*로직

- 주어진 입력 값들 저장. 입력값이 0일 경우에는 sudoku를 채우는 연산을 수행하기 위해 list에 저장. 입력값이 0이 아닌 경우에는 각각 row, column, box 배열에 비트 연산을 통해 현재 입력값이 있음을 알려줌

- sudoku를 채우는 연산을 수행. 빈칸에 idx라는 값을 넣었을 때 row,column,box 배열에 이미 들어있는 값과 겹치지 않는지 확인

- 겹치지 않는다면 idx 값을 넣고 다음 연산을 수행

- sudoku를 다 채우면 출력 후 종료

 

3. 코드

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

public class Main {

    public static int[] row = new int[9];
    public static int[] column = new int[9];
    public static int[] box = new int[9];
    public static ArrayList<Point> list = new ArrayList<>();
    public static int size = 0;
    public static int[][] sudoku_solve = new int[9][9];


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();



        for (int x = 0; x < 9; x++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int y = 0; y < 9; y++) {
                int now = Integer.parseInt(st.nextToken());

                if (now == 0) {
                    // 0인경우 리스트에 추가. 리스트 사이즈 증가
                    list.add(new Point(x, y));
                    size++;
                } else {

                    sudoku_solve[x][y] = now;

                    int bit = 1 << now;

                    // 열, 행, 박스에 현재 값(now)가 있음을 비트 연산으로 표시
                    row[x] |= bit;
                    column[y] |= bit;
                    box[x / 3 * 3 + y / 3] |= bit;

                }
            }
        }

        sudoku(0);

    }

    public static void sudoku(int x) {

        // 스도쿠 완성 시 출력하고 프로그램 종료
        if (x == size) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(sudoku_solve[i][j] + " ");
                }
                System.out.println();
            }

            System.exit(0);

        }

        Point now = list.get(x);

        for (int idx = 1; idx <= 9; idx++) {
            int bit = 1 << idx;

            // 행, 열, 박스에 idx 값이 없는가?
            if ((row[now.x] & bit) == 0 && (column[now.y] & bit) == 0 && (box[now.x / 3 * 3 + now.y / 3] & bit) == 0) {



                row[now.x] |= bit;
                column[now.y] |= bit;
                box[now.x / 3 * 3 + now.y / 3] |= bit;

                sudoku_solve[now.x][now.y] = idx;
                sudoku(x + 1);

                row[now.x] &= ~bit;
                column[now.y] &= ~bit;
                box[now.x / 3 * 3 + now.y / 3] &= ~bit;



            }
        }

    }

    static class Point{
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }



}