[BOJ/JAVA] 백준 2580번 스도쿠 ( 백트래킹 )

 

✔ 문제

난이도 : 골드4 🥇

2580번: 스도쿠

 

 

✔ 문제 풀이

 

실제 스도쿠 규칙과 같이 가로줄, 세로줄, 작은 정사격형 안의 수들이 1부터 9까지 하나씩 있어야합니다.

 

숫자가 입력 되었을 때 가로줄, 세로줄, 작은 정사각형을 탐색하여 중복된 숫자가 있는지 체크하는 로직은 쉽게 머리속에 떠올릴 수 있었지만, 어떤 흐름으로 어떤 조건을 사용하여 재귀호출하며 백트래킹 과정을 거칠지는 많이 고민이 필요한 문제였습니다.

 

 

 

🔎 isChecked

가로와 세로체크는 모든 9개의 범위를 탐색하여 같은 값이 있을 시 false를 반환합니다.

 

작은 사각형을 체크하려면 아래의 식을 수행 함으로써 0 or 3 or 6 이라는 값을 얻기 때문에 탐색해야 할 작은 사각형의 첫 좌표를 얻을 수 있습니다.

int startX = (x / 3) * 3
int startY = (y / 3) * 3

static boolean isChecked(int y, int x, int value){
    //가로 체크
    for( int i = 0; i<9; i++){
        if( square[y][i] == value ){
            return false;
        }
    }

    //세로 체크
    for( int i = 0; i<9; i++){
        if( i == y )continue;
        if( square[i][x] == value ){
           return false;
        }
    }

    //미니 사격형 체크
    int startX = (x / 3) * 3;
    int startY = (y / 3) * 3;
    for( int i = startY; i<startY + 3; i++){
        for( int j = startX; j<startX + 3; j++){
            if( square[i][j] == value ){
                return false;
            }
        }
    }

    return true;
}

 

 

🔎 재귀함수 sudoku

 

System.exit(0)를 통해 종료시켜 주는 이유는 경우의 수가 여러가지일 경우 한가지 경우만 출력하기 위함입니다.

자세한 설명은 주석을 통해 하겠습니다.

static void sudoku(int y, int x){

        // 가로 즉, 모든 행을 탐색했다면 다음 행으로 넘어가서 탐색합니다. sudoku(y + 1, 0);
        if( x == 9 ){
            sudoku(y + 1, 0);
            return;
        }

        /*
        * 모든 행, 열을 탐색하여 빈칸을 채웠다면 입력된 스도쿠 퍼즐을 출력합니다.
        * 재귀호출로 인해 연산이 계속될 수 있기 때문에 최초의 답을 출력하고 시스템을 종료합니다.
        */
        if( y == 9 ){
            for( int[] arr : square ){
                for( int i : arr){
                    sb.append(i).append(" ");
                }
                sb.append("\n");
            }

            System.out.println(sb);
            System.exit(0);
        }


        /*
        * 입력된 숫자가 0 이라면 즉, 비어있는 칸 이라면
        * 1~9까지 수 중에서 입력 가능한 수인지 isChecked 메소드를 통해 확인 후 숫자를 입력합니다. square[y][x] = i
        * 다음 칸 x축 으로 한칸 이동하여 다시 탐색을 이어갑니다. sudoku(y, x+1)
        * */
        if( square[y][x] == 0){
            for( int i = 1; i<=9; i++){
                if( isChecked(y, x, i)){
                    square[y][x] = i;
                    sudoku(y, x+1);
                }
            }
            // 다시 백트래킹하여 탐색해야 하기 때문에 비어있는 칸으로 되돌려 줍니다.
            square[y][x] = 0;
            return;
        }

        //비어있는 칸이 아니라면 바로 한칸 이동시켜 줍니다.
        sudoku(y, x + 1);

    }