[백준] 2580번(Java)

📖 스도쿠

[ 문제 ]

• 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
• 나머지 빈 칸을 채우는 방식은 다음과 같다.
  • 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
  • 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

💡풀이

• 필자는 HashSet을 사용해 9개의 가로줄들과 9개의 세로줄들, 3x3 크기의 블럭들 안에 값이 있는지를 확인했다. HashSet의 Contain의 시간 복잡도가 O(1)이기 때문에 다른 배열이나 리스트보다 훨씬 효율이 좋다고 생각해 이렇게 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] graph;
    static HashSet<Integer>[] rowIn;
    static HashSet<Integer>[] colIn;
    static HashSet<Integer>[] blockIn;
    static ArrayList<int[]> emp;
    static StringBuilder sb;

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

        graph = new int[9][9];
        emp = new ArrayList<>();

        rowIn = new HashSet[9];  // 가로 set
        colIn = new HashSet[9];  // 세로 set
        blockIn = new HashSet[9];  // 한 블럭 단위 set
        for(int k = 0 ; k < 9 ; k ++){
            rowIn[k] = new HashSet<>();
            colIn[k] = new HashSet<>();
            blockIn[k] = new HashSet<>();
        }

        for(int i = 0 ; i < 9 ; i ++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < 9 ; j ++){
                int n = Integer.parseInt(st.nextToken());
                graph[i][j] = n;
                if(n == 0){
                    emp.add(new int[]{i, j});
                } else {
                    rowIn[i].add(n);
                    colIn[j].add(n);
                    blockIn[(i/3) * 3 + j/3].add(n);
                }
            }
        }
        // 각 행, 열 별 , 각 블록 별 숫자들 넣어두기 -> HashSet으로 중복 있는지 없는지 검사
        btc(0, 0);
        System.out.println(sb);
    }
    public static void btc(int start, int cnt){
        if(cnt == emp.size()){
            sb = new StringBuilder();
            for(int a = 0 ; a < 9 ; a ++){
                for(int b = 0 ; b < 9 ; b ++){
                    sb.append(graph[a][b]).append(" ");
                }
                sb.append("\n");
            }
            return;
        }
        int row = emp.get(start)[0];
        int col = emp.get(start)[1];

        for(int j = 1 ; j < 10 ; j ++){
            if(!rowIn[row].contains(j) && !colIn[col].contains(j) && !blockIn[(row/3) * 3 + col/3].contains(j)){
                // 어디에도 포함이 안될 경우 -> 써도 되는 숫자구나!
                graph[row][col] = j;
                rowIn[row].add(j);
                colIn[col].add(j);
                blockIn[(row/3) * 3 + col/3].add(j);

                btc(start + 1, cnt + 1);

                graph[row][col] = 0;
                rowIn[row].remove(j);
                colIn[col].remove(j);
                blockIn[(row/3) * 3 + col/3].remove(j);

            }
        }
    }
}

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