[BOJ] 백준 [2580] 스도쿠 JAVA

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

2580번: 스도쿠

[문제]

[풀이]

스도쿠 요약 : 가로줄, 세로줄, 부분 정사각형 모두 1~9까지 숫자가 한번씩만 있어야 함.

백트래킹으로 접근해야한다
빈칸에 숫자하나 넣어보고 아니면 되돌아가서 다른숫자선택하고 ... 반복

1. 빈칸은 0으로 하므로 0인 좌표들을 List에 add 
2. List를 순회하면서 DFS 시작. 
3. 해당 좌표에 1~9 까지 숫자가 들어갈 수 있는지 확인.
4. DFS 의 depth가 List의 Size와 같으면 출력하고 종료.

import java.util.*;
import java.io.*;
import java.util.stream.*;
 
 
public class Main {
 
    static boolean finish;
    static ArrayList<Point> blankList = new ArrayList<>();
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[9][9];
 
        for(int i=0;i<9;i++) {
            map[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            for(int j=0;j<9;j++)
                if(map[i][j]==0) blankList.add(new Point(j,i));
        }
 
        fillNumber(0,0);
 
    }
 
    private static void fillNumber(int index,int depth) {
 
        if(depth==blankList.size()){
            print();
            finish = true;
        }
 
        if(finish) return;
 
        Point cur = blankList.get(index);
        for(int i=1;i<=9;i++){
            if(isPossible(cur,i)){
                map[cur.y][cur.x]=i;
                fillNumber(index+1,depth+1);
                map[cur.y][cur.x]=0;
            }
        }
    }
 
    private static boolean isPossible(Point cur, int num) {
 
        for(int i=0;i<9;i++){
            if(map[cur.y][i]==num || map[i][cur.x]==num)
                return false;
        }
 
        int nextX = cur.x/3*3, nextY = cur.y/3*3;
 
        for(int i=nextY;i<nextY+3;i++){
            for(int j=nextX;j<nextX+3;j++){
                if(map[i][j]==num) return false;
            }
        }
        return true;
    }
 
    private static void print() {
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++)
                System.out.print(map[i][j]+" ");
            System.out.println();
        }
    }
 
    static class Point{
        int x,y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}