[Dev-Ping9] 백준 2580번 - 스도쿠 (Java) [DFS] [반례 포함]

 

# 문제설명

 완전 탐색을 진행하면서 스도쿠 규칙에 맞는 조건만 끝까지 탐색한다.

 

 [스도쿠 규칙] 

 1. 가로 

 2. 세로

 3. 작은 사각형

 

# 접근 방법

 0(빈칸)의 갯수를 탐색해야 할 노드의 갯수로 정의한다.

 모든 노드를 dfs 방식으로 탐색하며, 조건에 맞지않을 경우 backtracking 한다. (마지막 노드에 도달한다면 그게 정답)

 

 

# 주의사항

 1. 답이 여러개일 경우에는 처음 발견된 답안을 출력한다.

   => 처음 발견된 답안을 출력하고 프로그램을 종료하여야 한다.  

 

 

# 코드구현 (반례 포함)

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

public class Main{
    static int [][] arr;
    static int [] blank;
    static int blankLen;

    static int whichSection(int n){
        if(n<3){
            return 0;
        }else if(n>=3 && n<6){
            return 1;
        }else{
            return 2;
        }
    }

    static boolean isPromising(int n, int m, int num){
        // 1. 가로 , 2. 세로 , 3. 작은 사각형
        int x = whichSection(n);
        int y = whichSection(m);
        // condition 1 
        for(int item : arr[n]){
            if(item == num) return false;
        }

        // condition 2
        for(int i=0; i<9; i++){
            if(arr[i][m] == num) return false;
        }

        // condition 3
        for(int i=(x*3);i<(x*3)+3;i++){
            for(int j= (y*3); j<(y*3)+3 ; j++){
                if(arr[i][j] == num) {
                    return false;}
            }
        }

        return true;
    }


    static void fillTheBlank_dfs(int nodeIdx){
        if(nodeIdx == blankLen){
            printArr(arr);
            //여러개일때 종료해야됨 ... ㅠㅠ
            System.exit(0);
            return;
        }

        int n = blank[nodeIdx]/9;
        int m = blank[nodeIdx]%9;
        for(int num=1; num<=9; num++){ //Time complexity : 9*blankLen
            if(isPromising(n, m, num)){
                arr[n][m] = num;
                fillTheBlank_dfs(nodeIdx+1);
                arr[n][m]=0; 
            }
        }
    }

    static void printArr(int [][] arr ){
        for(int i=0; i<arr.length; i++){
            for(int j=0; j<arr[0].length; j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        arr = new int[9][9];
        blank = new int[100];
        blankLen = 0;
        //init
        for(int i=0; i<9; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<9; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 0){
                    blank[blankLen++] = i*9 + j;
                }
            }
        }
        // System.out.println(blankLen);
        fillTheBlank_dfs(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 0
*/

/*
0 2 0 9 0 5 0 0 0
5 9 0 0 3 0 2 0 0
7 0 0 6 0 2 0 0 5
0 0 9 3 5 0 4 6 0
0 5 4 0 0 0 7 8 0
0 8 3 0 2 7 5 0 0
8 0 0 2 0 9 0 0 4
0 0 5 0 4 0 0 2 6
0 0 0 5 0 3 0 7 0
*/