BOJ_2580 : 스도쿠

👉 문제링크

2580번: 스도쿠

---

---

🔸 문제 분석 🔸

• 9x9 스도쿠 문제가 주어지면, 빈칸을 채워서 출력하는 문제이다.

🔸 문제 풀이 🔸

• 스도쿠 규칙에 따라 가로, 세로, 정사각형에 겹치는 숫자가 없도록 숫자를 채워가야 한다.
• 만약 숫자를 놓지 못하는 경우가 생기면, 직전에 놨던 숫자를 취소하고 다시 놓아 보아야 하기 때문에 백트래킹이 필요하다.
  • 백트래킹에서 가로, 세로, 정사각형에 겹치는 숫자가 있는지에 대한 상태 정보도 필요하다.
• 숫자를 채워가며 마지막 칸까지 채우는데 성공하면, 현재 상태를 출력한다.

🔸 코드 🔸

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

public class Main {
    private static final int size = 9;
    private static int[][] sdoku;
    private static boolean[][] row, col, square;

    private static int getSquare(int row, int col) {
        return (row / 3 * 3 + col / 3);
    }

    private static boolean game(int z) {
        if (z == 81) {
            return true;
        }

        int r = z / size;
        int c = z % size;

        if (sdoku[r][c] != 0) {
            return game(z + 1);
        } else {
            for (int i = 1; i <= 9; i++) {
                if (!row[r][i] && !col[c][i] && !square[getSquare(r, c)][i]) {
                    row[r][i] = col[c][i] = square[getSquare(r, c)][i] = true;
                    sdoku[r][c] = i;
                    if (game(z + 1)) {
                        return true;
                    }
                    sdoku[r][c] = 0;
                    row[r][i] = col[c][i] = square[getSquare(r, c)][i] = false;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        sdoku = new int[size][size];        // 스도쿠에 적힌 숫자
        row = new boolean[size][size + 1];      // 행에 나온 숫자 확인
        col = new boolean[size][size + 1];      // 열에 나온 숫자 확인
        square = new boolean[size][size + 1];   // 정사각형에 나온 숫자 확인

        for (int i = 0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < size; j++) {
                sdoku[i][j] = Integer.parseInt(st.nextToken());
                row[i][sdoku[i][j]] = true;
                col[j][sdoku[i][j]] = true;
                square[getSquare(i, j)][sdoku[i][j]] = true;
            }
        }

        // 백트래킹
        game(0);

        // Output
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                sb.append(sdoku[i][j]).append(' ');
            }
            sb.append('\n');
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 스도쿠 게임판 상태를 int형 이중배열 sdoku에 기록해가며 풀이한다.
• 가로, 세로, 정사각형에 나타난 숫자를 체크하기 위해 boolean 이중배열 row, col, sqaure를 사용한다.
• 재귀 메서드 game() 에서 백트래킹을 통해 스도쿠를 플레이한다.
  • 스도쿠 칸의 번호 z를 넘겨 81개의 칸을 모두 채우는데 성공하면 true를 반환한다.
  • z를 스도쿠 한변의 길이 size로 나누거나 몫을 구해 좌표를 구한다.
  • 만약 숫자가 채워져있으면 넘어가고, 빈칸(0)이면 1부터 9까지 하나씩 채워본다.
    • 숫자를 채울 때, 가로 / 세로 / 정사각형에 겹치는 숫자가 없는지 확인한다.
    • 등장한 숫자로 체크해주고, z+1로 game을 다시 재귀한다.
    • 만약 모든 탐색에 실패했다면, 현재 칸을 0으로 다시 비워주고, 등장한 숫자에서도 지워준 뒤 false를 반환한다.
• game() 메서드의 모든 재귀가 마무리 된 뒤, sdoku 배열을 출력한다.

---

🔸 end 🔸

• 문제 설명에 12095 : 가장 오래 걸리는 스도쿠 문제의 소스로 풀 수 있는 입력만 주어진다길래, 찾아가보니 정답 코드가 있었다... 문제를 풀기도 전에 스포당했는데, 좋은 예시 코드를 보고 클론코딩 하듯 풀이해 보았다.
• 풀이 원리 자체는 백트래킹을 구현하는거라 간단했다. 연계되는 12095 문제도 다음에 꼭 풀어보도록 하자.