백준2580 스도쿠

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

2580번: 스도쿠

정말 오랜만에 엄청 어려운 문제를 만나서 고생을 했다. 혼자 힘으로 문제를 풀어내려고 했지만 결국 풀 수 없었고 3x3박스 검사하는 부분을 생각해내는 것도 어려웠다.

 처음에 평범한 백트래킹 문제라고 생각하고 모든경우를 다 탐색하고 조건을 만족하는 경우 출력을 시키려고 했지만 정답이 나오지 않아서 칸이 비어있는 즉 0인 부분의 좌표를 찾아서 그부분에 1~9 사이의 수를 넣으면 행,열,박스를 만족하면 다음 빈칸을 찾는 방식으로 문제를 해결하는 것이라는 것을 깨달았다.

 하지만 그렇게 풀어도 런타임에러가 나와서 검사해야할 3가지 조건에 대한 2차원 배열 3개를 만들어서 풀었다. 

 행,열,박스를 검사하는 배열의 각 행에는 1~9까지 숫자가 모두 사용되었는지 확인하기위하여 사용되었다. 예를 들면 스도쿠 0행에 3이 있다면 행을 검사하는 배열  chk_row[0][3] = true; 가 되도록 하였다. 

정말 잘하는 분들이 너무 많은 것 같다... 열심히 해야겠다!

 

package 백트래킹;
import java.util.*;
class Node{
    int x;
    int y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class 스도쿠_정답 {
    static boolean [][] chk_col = new boolean[9][10]; // 행
    static boolean [][] chk_row = new boolean[9][10]; // 열
    static boolean [][] chk_box = new boolean[9][10]; // 3x3박스검사
    public static boolean sd(int[][] arr,int count,ArrayList<Node> nodes,int idx){
        if(idx>=count){
            for(int i=0;i<9;i++){
                for (int j = 0; j < 9; j++) {
                    System.out.print(arr[i][j]+" ");
                }
                System.out.println();
            }
            return true;
        }
        Node node = nodes.get(idx);
        for (int i = 1; i <=9 ; i++) { //1부터 9까지 모든 경우
            if(chk_col[node.x][i])
                continue;
            if(chk_row[node.y][i])
                continue;
            if(chk_box[(node.x/3)*3+(node.y)/3][i]) //3x3을 하나의 열로 저장해둔것
                continue;
 
            chk_col[node.x][i] = true;
            chk_row[node.y][i] = true;
            chk_box[(node.x/3)*3+(node.y)/3][i]=true;
            arr[node.x][node.y] = i;
            if(sd(arr,count,nodes,idx+1))
                return true; //탐색종료
 
            arr[node.x][node.y] = 0;//이전으로 돌려놓기
            chk_col[node.x][i] = false;
            chk_row[node.y][i] = false;
            chk_box[(node.x/3)*3+(node.y)/3][i]=false;
 
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int[][] sd=new int[9][9];
 
        int count=0;
        ArrayList<Node> nodes=new ArrayList<Node>();
 
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                sd[i][j]=scan.nextInt();
                if(sd[i][j]==0) {
                    count++;
                    nodes.add(new Node(i,j));
                }
                else {
                    chk_col[i][sd[i][j]]=true;
                    chk_row[j][sd[i][j]]=true;
                    chk_box[(i/3)*3+(j/3)][sd[i][j]]=true;
                }
            }
        }
        sd(sd, count, nodes, 0);
    }
}
 

 

참고한 블로그 https://a1010100z.tistory.com/81

[백준 알고리즘 -2580] 스도쿠 - java (백트래킹)

처음 풀이

 

package 백트래킹;
 
import java.io.*;
import java.util.*;
 
class P {
    int x, y;
 
    public P(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class 스도쿠 {
    static int[][] board = new int[10][10];
    static int countBlank = 0;
    static ArrayList<P> blank = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        for (int i = 1; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < 10; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 0) {
                    countBlank++;
                    blank.add(new P(i, j));
                }
            }
        }
 
        fun(0);
 
    }
 
    static void fun(int idx) {
        if (idx == blank.size()) {
            for (int i = 1; i < 10; i++) {
                for (int j = 1; j < 10; j++) {
                    System.out.print(board[i][j]+" ");
                }
                System.out.println();
            }
            System.exit(1);
            return;
 
        }
        P p = blank.get(idx);
        for (int i = 1; i < 10; i++) {
            if (isValid(p.x, p.y, i)) {
                board[p.x][p.y] = i;
                fun(idx + 1);
                board[p.x][p.y] = 0;
            }
        }
    }
 
    private static boolean isValid(int x, int y, int target) {
        for (int j = 1; j < 10; j++) { //가로 세로 확인
            if (target == board[j][y] || board[x][j] == target) return false;
        }
        int k = (x-1) / 3*3 +1 ;//작은블럭 확인
        int l = (y-1) / 3*3 +1;
        for (int i = 0; i <3 ; i++) {
            for (int j = 0; j <3 ; j++) {
                if(board[i+k][j+l]==target) return false;
            }
        }
 
        return true;
    }
 
 
}