백준 2239 스도쿠 - JAVA

2239 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
 
public class Main {
    static int[][] sudoku;
    static boolean[][][] visit;
    static boolean success;
    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();
        
        sudoku = new int[9][9]; // 마지막이 10 인 이유는 스도쿠의 숫자가 들어가는 자리이므로 (1 - base - position)
        visit = new boolean[3][9][10];
        for (int i = 0; i < 9; i++) {
            String input = br.readLine();
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = input.charAt(j) - '0';
                if (sudoku[i][j] != 0) {
                    visit[0][i][sudoku[i][j]] = true;
                    visit[1][j][sudoku[i][j]] = true;
                    visit[2][(i/3)*3+(j/3)][sudoku[i][j]] = true;
                } 
            } 
        } 
        findNum(0, 0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(sudoku[i][j]);
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }
    private static void findNum(int x, int y) {
        if (x == 8 && y == 8) {
            for (int i = 1; i <= 9; i++) {
                if (!visit[0][8][i]) {
                    sudoku[x][y] = i;
                    break;
                } 
            } 
            success = true;
            return;
        } 
        if (sudoku[x][y] != 0) {
            if(y != 8) {
                findNum(x, y+1);
            } else {
                findNum(x+1, 0);
            }
        } else {
            for (int i = 1; i <= 9; i++) {
                if (!visit[0][x][i] && !visit[1][y][i] && !visit[2][(x/3)*3 + (y/3)][i]) {
                    visit[0][x][i] = true;
                    visit[1][y][i] = true;
                    visit[2][(x/3)*3 + (y/3)][i] = true;
                    sudoku[x][y] = i;
                    if (y != 8) {
                        findNum(x, y+1);
                    } else {
                        findNum(x+1, 0);
                    }
                    if (success) {
                        return;
                    } 
                    sudoku[x][y] = 0;
                    visit[0][x][i] = false;
                    visit[1][y][i] = false;
                    visit[2][(x/3)*3+(y/3)][i] =false;
                }
            } 
        }
    }
}

 

알고리즘 설명

---

 

참 어려운 문제였습니다. visit 배열을 3차원 배열로 만들어, visit[0][][]은 열, visit[1][][]은 행, visit[2][][]은 박스로 나누어 행과 열과 3*3박스 배열에 중복되지 않는 수(배열의 인덱스 값이 false인 숫자) 부터 숫자를 채워나가면서 진행이 불가능 할 때, 백트래킹으로 다시 가능한 경우의 수부터 시작하는 알고리즘입니다.

백트래킹의 핵심은 종료점을 명확히 정의하는 것입니다. 이 부분이 생각보다 쉽지 않았습니다... (0,0)부터 시작해서, visit[0]과 visit[1]과 visit[2] 세개의 배열에서 모두 false인 숫자부터 sudoku 배열을 채워나갑니다. 이때, 경우의 수를 위해 백트래킹을 사용하는데, 완성이 불가능하도록 숫자가 채워졌을 때, 종료할 종료점과 스도쿠가 이미 완성되었는데도, 이미 호출되어서 실행되고 있는 함수를 종료할 종료점을 잘 생각해가며 문제를 풀어야 합니다. 백트래킹을 통해 최적의 해를 찾으며, 불가능한 경로는 빠르게 포기하여 불필요한 연산을 최소화하는 것이 이 알고리즘의 핵심입니다. 어렵지만 생각을 깊게하게 해주는 좋은 문제였던 것 같습니다.

 

코드 해석

---

9×9 스도쿠 판을 입력받아 sudoku[][]배열에 저장하고, 동시에 각 숫자가 속한 행, 열, 그리고 3×3 박스에서 사용된 숫자를 기록하는 visit 배열을 입력에 맞게 초기화합니다. 이후 백트래킹을 이용해 findNum 함수를 호출하여 빈 칸을 채워나갑니다.

 

findNum 함수는 현재 위치 (x, y)가 마지막 칸 (8, 8)에 도달하면 해당 칸에 넣을 수 있는 숫자를 찾고 종료 플래그(success)를 설정한 후 재귀를 종료합니다. 만약 현재 위치가 이미 숫자가 채워져 있는 경우 다음 위치로 이동하며, (y != 8)일 경우 y를 증가시키고 (y == 8)이면 x를 증가시키면서 다음 줄의 첫 번째 칸으로 이동합니다. 빈 칸인 경우 1~9까지의 숫자를 시도하며, 해당 숫자가 현재 행, 열, 3×3 박스에 없는 경우 visit 배열을 갱신하고 숫자를 채운 뒤 재귀 호출을 통해 다음 칸을 채웁니다.

 

만약 이후 진행이 불가능한 경우, 즉 유효한 스도쿠 상태를 만들 수 없는 경우에는 백트래킹을 수행하여 다시 빈 칸으로 되돌리고, visit 배열을 원래 상태로 복구한 뒤 다음 숫자를 시도합니다. 가능한 모든 경우의 수를 탐색하며 유효한 해를 찾으면 최종적으로 완성된 스도쿠 판을 출력한다.

 

코드에서 success가 두 번 사용되는 이유는 스도쿠가 완성된 이후 불필요한 탐색을 방지하기 위함입니다.
첫 번째 success는 마지막 칸 (8, 8)에서 스도쿠를 완성했을 때 true로 설정하여 findNum()함수를 안전하게 종료시키는 용도이고, 두번째 success(64~66줄)는 스도쿠가 이미 완성된 상태임에도, 재귀로 인한 함수 호출을 막는 즉, 불필요한 탐색을 종료시키는 용도라고 생각하면 될것 같습니다.