BOJ_2239 : 스도쿠

👉 문제링크

2239번: 스도쿠

---

---

🔸 문제 분석 🔸

•  9 x 9 스도쿠의 빈칸을 채우는 문제이다.
  • 스도쿠는 가로, 세로, 소속 3x3 칸에 중복되는 숫자가 없어야 한다. 
  • 여러 개의 답 중 사전식으로 앞서는 것을 출력한다.
• 그리디하게 접근해서 좌상단부터 우하단으로 넣을 수 있는 작은 수들을 넣다보면 넣을수 없는 경우가 생긴다.
  • 따라서 넣을 수 없는 경우는 다시 돌아가서 다음 숫자를 넣어봐야 하므로 백트래킹을 사용한다.

🔸 코드 🔸

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

public class Main {
    private static int[][] map;

    private static boolean recu(int n) {
        if (n == 81) return true;

        int r = n / 9;
        int c = n % 9;

        if (map[r][c] != 0) return recu(n + 1);
        else {
            boolean[] used = new boolean[10];

            for (int k = 0; k < 9; k++) {
                used[map[r][k]] = true; // check row
                used[map[k][c]] = true; // check col
            }

            // check 3x3
            int x = r / 3 * 3;
            int y = c / 3 * 3;
            for (int k = x; k < x + 3; k++) {
                for (int l = y; l < y + 3; l++) {
                    used[map[k][l]] = true;
                }
            }

            for (int k = 1; k <= 9; k++) {
                if (!used[k]) {
                    map[r][c] = k;
                    if (recu(n+1)) return true;
                }
            }
            map[r][c] = 0;
            return false;
        }
    }

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[9][9];
        for (int i = 0; i < 9; i++) {
            String[] ss = br.readLine().split("");
            for (int j = 0; j < 9; j++) {
                map[i][j] = Integer.parseInt(ss[j]);
            }
        }

        // Sudoku
        recu(0);

        // Output
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(map[i][j]);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

🔸 코드 해석 🔸

• 재귀 메서드 recu를 통해 스도쿠를 채워 나간다.
  • 81칸을 모두 채우면 성공이므로 재귀를 종료한다. (true 리턴)
  • 스도쿠 판에서 행과 열을 n의 목과 나머지로 접근한다.
    • 이미 값이 채워져 있으면 다음 칸을 확인한다.
  • 채워져 있지 않다면, 가로/세로/3x3을 확인해서 등장한 숫자를 used 배열에 인덱스로 true를 저장한다.
  • 넣을 수 있는 값을 작은 순으로 넣어보고 재귀로 넘긴다.
    • 만약 성공했으면 종료, 실패하면 다음 값을 넣는다.
• 재귀 종료 후 스도쿠판을 출력한다.
  • 불가능한 경우는 없다.

---

🔸 end 🔸

• 처음엔 그리디로 접근해서 값을 찾지 못한 0인 부분들이 부분부분 나타났다.
  • 디버깅 과정에서 백트래킹이 필요하다는 사실을 알고 코드를 수정했다.