[백준]2580. 스도쿠 - Java

📄 링크

스도쿠

---

💡 문제 분석

• 9 * 9 스도판의 빈칸을 완성하는 문제
• 총 81칸이므로 첫 칸부터 순서대로 다 돌아보며 가로, 세로, 3 * 3 배열에 동시에 없는 숫자를 넣어봅니다.
• 전형적인 백트래킹 문제
• 모든 칸을 성공했다면 출력
• 여러가지 답이 있을 수 있기 때문에 한 개만 출력하기 위해 System.exit() 사용

---

⌨️ 코드

public class _2580_스도쿠 {
    static int[][] map;
    static boolean[][] col, row, square;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        map = new int[9][9];
        col = new boolean[9][10];
        row = new boolean[9][10];
        square = new boolean[9][10];
        for(int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] != 0)
                    col[j][map[i][j]] = row[i][map[i][j]] = square[getIdx(i, j)][map[i][j]] = true;
            }
        }
        backtracking(0);
    }

    static void backtracking(int cnt) {
        if(cnt == 81) {
            for(int[] a : map) {
                for(int b : a)
                    System.out.print(b + " ");
                System.out.println();
            }
            System.exit(0);
        }
        int y = cnt / 9;
        int x = cnt % 9;
        if(map[y][x] != 0) backtracking(cnt + 1);
        else {
            for(int k = 1; k <= 9; k++) {
                if(col[x][k] || row[y][k] || square[getIdx(y, x)][k]) continue;
                map[y][x] = k;
                col[x][k] = row[y][k] = square[getIdx(y, x)][k] = true;
                backtracking(cnt + 1);
                col[x][k] = row[y][k] = square[getIdx(y, x)][k] = false;
            }
        }
    }

    static int getIdx(int y, int x) {
        return (y / 3) * 3 + x / 3;
    }

---

📋 결과