백준 2580 스도쿠 (java)

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

 

9*9 판에 숫자들을 입력받고 빈칸(0이 입력된 칸)에 스도쿠 규칙에 맞게 채워야 하는 문제.

일단 빈칸들을 돌면서 가능한 값을 넣어보고 그렇게 해나가다가 어떻게해도 안되는 칸이 생기면

앞에 한 것으로 돌아와서 다른 값을 넣어보는 방식으로 구현하기로 했다.

백트래킹 방식.

 

아래는 구현한 코드.

처음 제출시에는 solve 끝쪽에 return;을 생략했다가 틀렸다.

백트래킹 방식을 채택했기에, 1~9 다 넣어보는 모든 수를 다 해봐도 뭔가 해결이 되지 않으면 앞으로 돌아가보아야 하는데

return을 생략해서 그냥 아무것도 하지 않고 다음으로 넘어가는 흐름이 되어버렸었다.

import java.util.*;
import java.io.*;

class Main
{

    /*
    한칸을 채우는데 고려할 사항은, 여기에 이걸 넣었을 때, 해당 행에 같은게 있으면 안돼
    해당 열에 같은게 있으면 안돼 해당 칸에 속한 아홉개짜리에 겹치는게 있으면 안돼.
    백트래킹으로 접근하자. 0인 칸을 모두 따로 저장한다. 해당 칸에 1부터 9까지 돌면서 해보고
    제한사항에 걸린게 있으면 return해서 그건 넘겨.
    */
    static int[][] arr = new int[9][9];
    static class point{
        public int row;
        public int col;
        point(){};
        point(int row,int col){this.row= row;this.col=col;}
    }
    static ArrayList<point> zeros = new ArrayList<>();
    static void pr(){
        for(int p=0;p<9;p++){
            for(int q=0;q<9;q++){
                System.out.print(arr[p][q]+" ");
            }
            System.out.println();

        }
        System.out.println();
    }
    static boolean[] visited=null;
    static void solve(int startindex){
        for(int i=startindex;i<zeros.size();i++){
            point temppoint=zeros.get(i);
            for(int j=1;j<=9;j++){
                int result=0;
                if(i<zeros.size()-1){
                    result=check(0,temppoint,j);
                }
                else{
                    result=check(1,temppoint,j);
                }
                if(result==1){
                    //pr();
                    solve( i+1);
                }
                else if(result==2) {
                    pr();
                    System.exit(0);
                }
            }
            arr[temppoint.row][temppoint.col]=0;
            return;
        }
    }
    static int check(int com, point p,int input){
        int[]check=new int[10];
        int data = arr[p.row][p.col];
        for(int i=0;i<9;i++){
            int num = arr[i][p.col];
            if(num==input){
                return 0;
            }

        }
        Arrays.fill(check,0);
        for(int i=0;i<9;i++){
            int num = arr[p.row][i];
            if(num==input){
                return 0;
            }
        }
        Arrays.fill(check,0);
        int startrow=(p.row/3)*3;
        int startcol=(p.col/3)*3;
        for(int i=startrow;i<startrow+3;i++){
            for(int j=startcol;j<startcol+3;j++){
                int num = arr[i][j];
                if(num==input){
                    return 0;
                }
            }
        }
        arr[p.row][p.col]=input;
        if(com==0)return 1;
        else return 2;

    }
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int i=0;i<9;i++){
            String str = br.readLine();
            StringTokenizer token = new StringTokenizer(str);
            for(int j=0;j<9;j++){
                arr[i][j]=Integer.parseInt(token.nextToken());
                if(arr[i][j]==0){
                    zeros.add(new point(i,j));
                }
            }
        }
        visited = new boolean[zeros.size()];
        //System.out.println(zeros.size());
        solve(0);



    }
}