백 준 - 2580

문제 : www.acmicpc.net/problem/2580

2580번: 스도쿠

문제는 다음과 같습니다.

 

문제의 핵심은 스도쿠에서 몇 칸이 0으로 변경된 입력이 주어지면 해당 입력을 적절한 값으로 채워서 스도쿠를 완성하는 것입니다.

여기서 스도쿠가 만들어질 수 있는 경우만 입력이 되므로 저희는 백트랙킹 즉 모든 경우를 하나하나 검사하면서 경우를 충족하지 못하면 해당 경우를 삭제하도록 하는 방법을 생각해볼 수 있습니다.

 

경우를 삭제하는 것은 스도쿠의 규칙 , 열, 행 그리고 주위 구역에서의 1,2,3,4,5,6,7,8,9 에서 중복된 수가 있는가? 입니다.

 

해서 주어진 제한조건에 어긋나지 않다면 해당 칸에 값을 채우고 다음 칸으로 이동하는 식으로 제귀를 구현할 수 있습니다. 과정을 정리하면 다음과 같습니다. 

 

전체적인 코드는 다음과 같습니다.

import java.util.*;

public class Main {

    //문제 2580

    public static boolean first = false;

    public static int[][] ans = new int[9][9];

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int[][] arr = new int[9][9];

        for (int i = 0 ; i < 9 ; i++) {

            for(int j = 0 ; j < 9 ; j++) {

                arr[i][j] = stdin.nextInt();
            }
        }

        recursive(arr , 0 , 0);

        for(int i = 0 ; i < ans.length ; i++) {

            for(int j = 0 ; j < ans.length ; j++) {

                System.out.print(ans[i][j] + " ");
            }

            System.out.println();
        }

    }

    public static void recursive(int[][] arr , int x , int y) {

        if( x == 0 && y == arr.length) {

            if (first == false) {

                for(int i = 0 ; i < ans.length ; i++) {

                    for(int j = 0 ; j < ans.length ; j++) {

                        ans[i][j] = arr[i][j];
                    }
                }

                first = true;
            }

            return;
        }

        if (arr[y][x] == 0) {

            for (int i = 1; i < 10 ; i++) {

                arr[y][x] = i;

                if ((check1(arr , x)) && check2(arr, y) && check3(arr , x , y)) {

                    if (x == arr.length-1) {

                        recursive(arr , 0 , y+1);
                    }
                    else {

                        recursive(arr , x+1 , y);
                    }
                }

                arr[y][x] = 0;
            }
        }
        else {

            if (x == arr.length-1) {

                recursive(arr , 0 , y+1);
            }
            else {

                recursive(arr , x+1 , y);
            }

        }

    }

    public static boolean check1(int[][] arr , int x) {

        boolean[] flag = new boolean[10];

        for (int i = 0 ; i < arr.length ; i++) {

            int num = arr[i][x];

            if (flag[num] == false) {

                flag[num] = true;
            }
            else {
                if (num != 0)
                    return false;
            }
        }

        return true;
    }

    public static boolean check2(int[][] arr , int y) {

        boolean[] flag = new boolean[10];

        for (int i = 0 ; i < arr.length ; i++) {

            int num = arr[y][i];

            if (flag[num] == false)
                flag[num] = true;
            else{
                if (num != 0)
                    return false;
            }
        }

        return true;

    }

    public static boolean check3(int[][] arr , int x , int y) {

        int ptrX = (x/3) + 1;

        int startX = ptrX * 3 - 3;
        int lastX = ptrX * 3;

        int ptrY = (y/3) + 1;

        int startY = ptrY * 3 - 3;
        int lastY = ptrY * 3;

        boolean[] flag = new boolean[10];

        for (int i = startY ; i < lastY ; i++) {

            for (int j = startX ; j < lastX ; j++) {

                int val = arr[i][j];

                if (flag[val] == false)
                    flag[val] = true;
                else{
                    if (val != 0)
                        return false;
                }
            }
        }

        return true;
    }

}