[코딩테스트 합격자 되기(Java)] 문제 44.스도쿠 퍼즐★★★

문제

9 x9 스도쿠 보드를 다 채워 완성된 스도쿠 보드를 반환하는 solution()함수를 작성하세요.

해는 유일하지 않을 수 있습니다. 스도쿠의 조건에 맞다면 맞는 해라고 생각하시면 됩니다.

스도쿠의 규칙은 아래와 같습니다.

1. 가로줄, 세로줄에는 1부터 9까지의 숫자가 한번씩 나타나야 합니다.
2. 9x9 보드를 채울 9개의 작은 박스(3 x3크기)에도 1부터 9까지의 숫자가 한번씩 나타나야합니다.

 

 

제약조건

문제에 주어지는 board 중 스도쿠를 완성하지 못하는 board는 없다고 가정합니다.

예를들어, 특정행이나 열에 같은 숫자가 있는 경우는 없습니다.

 

 

 

입출력 예시

board	result
[ [5, 3, 0, 0, 7, 0, 0, 0, 0], [6, 0, 0, 1, 9, 5, 0, 0, 0], [0, 9, 8, 0, 0, 0, 0, 6, 0], [8, 0, 0, 0, 6, 0, 0, 0, 3], [4, 0, 0, 8, 0, 3, 0, 0, 1], [7, 0, 0, 0, 2, 0, 0, 0, 6], [0, 6, 0, 0, 0, 0, 2, 8, 0], [0, 0, 0, 4, 1, 9, 0, 0, 5], [0, 0, 0, 0, 8, 0, 0, 7, 9] ]	[ [5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9], ]
[ [0, 0, 0, 0, 0, 0, 0, 0, 0],  [0, 0, 0, 0, 0, 0, 0, 0, 0],  [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0],  [0, 0, 0, 0, 0, 0, 0, 0, 0],  [0, 0, 0, 0, 0, 0, 0, 0, 0],  [0, 0, 0, 0, 0, 0, 0, 0, 0],  [0, 0, 0, 0, 0, 0, 0, 0, 0],  [0, 0, 0, 0, 0, 0, 0, 0, 0], ]	[ [1, 2, 3, 4, 5, 6, 7, 8, 9], [4, 5, 6, 7, 8, 9, 1, 2, 3],  [7, 8, 9, 1, 2, 3, 4, 5, 6],  [2, 3, 4, 5, 6, 7, 8, 9, 1],  [5, 6, 7, 8, 9, 1, 2, 3, 4],  [8, 9, 1 , 2, 3, 4, 5, 6,7], [3, 4, 5, 6, 7, 8, 9, 1, 2],  [6, 7, 8, 9, 1, 2, 3, 4, 5], [9, 1, 2, 3, 4, 5, 6, 7, 8] ]

 

 

 

문제 풀이

비어있는 칸(0인 칸)에 숫자를 넣기 위해서는 백트래킹 방식으로 문제를 해결할 수 있다.

넣으려는 숫자 num에 대해 백트래킹 조건을 정의하면 다음과 같다.

1. 같은 행에 num이 있으면 백트래킹.

2. 같은 열에 num이 있으면 백트래킹.

3. (3*3)으로 나뉜 작은 박스 안에 num이 있으면 백트래킹.

탐색하는 위치에 대하여 백트래킹 조건에 걸리지 않으면 num을 넣어준다.

 

import java.util.*;

class Solution{
    int[][] board;
    List<int[]> empty; // 비어있는 칸 {row, col}
    void init(int[][] board){ // board, empty 초기화
        this.board = board;
        empty = new ArrayList<>();
        for(int row=0; row<9; row++){
            for(int col=0; col<9; col++){
                if(board[row][col] == 0) empty.add(new int[]{row, col});
            }
        }
    }

    // 백트래킹 조건 확인하는 함수. true면 백트래킹
    boolean conditionCheck(int row, int col, int num){
        for(int i=0; i<9; i++){
            if(board[row][i] == num || board[i][col] == num) return true; // 같은 행 또는 열에 num이 있음
            if(i<3){ // 같은 3x3박스에 num이 있음
                if(board[(row/3)*3+i][(col/3)*3+0] == num) return true;
                if(board[(row/3)*3+i][(col/3)*3+1] == num) return true;
                if(board[(row/3)*3+i][(col/3)*3+2] == num) return true;
            }
        }
        return false;
    }

    // 백트래킹 함수
    boolean backtracking(int emptyIdx, int num){
        if(emptyIdx == empty.size()) return true; // 빈 칸 다 채웠으면 끝. true 리턴
        int[] cur = empty.get(emptyIdx); // 값 채워줄 빈칸 꺼내기
        if(conditionCheck(cur[0], cur[1], num)){ // 백트래킹 조건 확인
            return false;
        }

        board[cur[0]][cur[1]] = num; // board에 값 채워주기

        // 재귀하여 다음 빈 칸 확인
        for(int n = 1; n <= 9; n++){
            if(backtracking(emptyIdx+1 ,n)) return true; // 리턴값이 true면 탐색 중지
        }

        board[cur[0]][cur[1]] = 0; // 백트래킹 되었으면 값 0으로 돌려놓기
        return false;
    }


    int[][] solution(int[][] board){
        init(board);
        for(int num = 1; num <= 9; num++){ // 첫번째 빈 칸에 1부터 값 넣어보기
            if(backtracking(0, num)) break;
        }
        return board;
    }
}