[JAVA] 백준 스도미노쿠 4574

www.acmicpc.net/problem/4574

4574번: 스도미노쿠

1. 스도쿠에서 방문 체크하기

 

9*9 스도쿠에서 임의의 점 (x,y) 에 숫자 num을 넣을 수 있는지 없는지 어떻게 판단할까??

 

처음 생각했던 건 x행에 num이 존재하는지 검사하고 y열에 num이 존재하는지 검사하고 마지막으로 9*9 를 3*3 으로 나눈 각각의 박스에서 num이 존재하는지 확인하는 것이다. 별로 좋지 못한 방법이다.

 

더 좋은 방법이 있다.

0행에 8이 존재하는가? 이 말은

boolean[] c1 = new boolean[10][10];
if(c1[0][8]) ...

위 코드처럼 쓸수 있다.

 

마찬가지로 

2열에 3이 존재하는가? 이 말은

boolean[] c2 = new boolean[10][10];
if(c2[2][3]) ...

이렇게 쓸수 있다.

 

그리고 9*9 스도쿠에서 자신이 속한 (3*3)박스를 어떻게 구하는가?

 

9*9 행렬의 원소 (x,y) 는 3*3 행렬로 바꾼다면 (x/3,y/3) 에 대응된다.

 

9*9 행렬의 원소 (x,y) 의 번호는 9*x + y 다. 즉 (0,0)의 번호는 9*0 + 0 = 0 이며 (8,8) 의 번호는 8*9 + 8 = 80이다.

0번부터 80번까지 총 81칸을 확인할 수 있다.

 

9*9 행렬의 원소 (x,y) 의 번호가 9*x + y 라면 3*3 행렬의 번호는 3*(x/3) + (y/3) 이다.

 

따라서 9*9 행렬의 원소 (2,3) 가 속한 박스에 8번이 존재하는가? 이 말은 아래와 같다.

boolean[] c3 = new boolean[10][10];
if(c3[3*(2/3) + (3/3)][8]) ...

참고로 박스는 0번부터 8번까지 총 9개 존재한다.

 

 

 

2. 시뮬레이션의 주체는?

 

도미노를 기준으로 놓을 것인가? 아니면 스도쿠 판에서 한 칸의 위치를 기준으로 놓을 것인가? 문제다.

다시말하면, dfs 에서 종료조건이 도미노인 (1,2) ~ (8,9) 를 기준으로 종료할 것인지 아니면 (0,0) ~ (8,8) 까지 스도쿠의 한칸한칸 위치를 기준으로 할것인지 문제다. 둘 다 가능하지만 후자가 더 빠른거 같다.

 

dfs 는 후자이며 

dfs2 는 전자이다.

 

코드는 아래와 같다.

import java.util.*;

class Main{
    static int[][] map ;
    static boolean[][] block;
    static int n;
    static int[] dx = new int[]{0,1};
    static int[] dy = new int[]{1,0};
    static boolean[][] c1 ;
    static boolean[][] c2 ;
    static boolean[][] c3 ;
    static boolean flag ;


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a,b;
        int tc = 1;
        char[] chArr;
        while(true){
            flag = false;
            n = sc.nextInt();
            block = new boolean[10][10];
            map = new int[9][9];
            c1 = new boolean[10][10];
            c2 = new boolean[10][10];
            c3 = new boolean[10][10];
            if(n == 0) break;
            for(int i=0;i<n;i++){
                a = sc.nextInt();
                chArr = sc.next().toCharArray();
                int l1 = chArr[0]-'A';
                int l2 = chArr[1]-'1';
                map[l1][l2] = a;
                checking(l1,l2,a,true);

                b=sc.nextInt();
                chArr = sc.next().toCharArray();
                l1 = chArr[0]-'A';
                l2 = chArr[1]-'1';
                map[l1][l2] = b;
                checking(l1,l2,b,true);

                block[a][b] = true;
                block[b][a] = true;
            }
            for(int i=1;i<10;i++){
                chArr = sc.next().toCharArray();
                int l1 = chArr[0]-'A';
                int l2 = chArr[1]-'1';
                map[l1][l2] = i;
                checking(l1,l2,i,true);
            }
            System.out.println("Puzzle "+tc);
            tc++;
            dfs(0);

        }
    }

    static void dfs2(int a,int b){ // (1,2) - (8,9)
        if(a==9) {
            if(!flag) {
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++) {
                        System.out.printf("%d", map[i][j]);
                    }
                    System.out.println();
                }
                flag = true;
            }
            return;
        }
        int na=a,nb=b+1;
        if(nb>9){
            ++na; nb=na+1;
        }
        if(block[a][b]) {
            dfs2(na,nb);
        }
        else{
            // a,b 도미노를 어디다 놓아야 하는가??
            int ni,nj;
            for(int k =0 ;k < 2 ;k ++) {
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++) {
                        ni = i + dx[k];
                        nj = j + dy[k];
                        if(!rangeCheck(ni,nj)) continue;
                        if(map[i][j]!=0) continue;
                        if(map[ni][nj]!=0) continue;
                        if(can(i,j,a) && can(ni,nj,b)){
                            map[i][j] = a;
                            map[ni][nj] = b;
                            block[a][b] = block[b][a]=true;
                            checking(i,j,a,true);
                            checking(ni,nj,b,true);
                            if(!flag)
                                dfs2(na,nb);
                            block[a][b] = block[b][a]=false;
                            checking(i,j,a,false);
                            checking(ni,nj,b,false);
                            map[i][j]=0;
                            map[ni][nj]=0;
                        }
                        if(can(i,j,b) && can(ni,nj,a)){
                            map[i][j] = b;
                            map[ni][nj] = a;
                            block[a][b] = block[b][a]=true;
                            checking(i,j,b,true);
                            checking(ni,nj,a,true);
                            if(!flag)
                                dfs2(na,nb);
                            block[a][b] = block[b][a]=false;
                            checking(i,j,b,false);
                            checking(ni,nj,a,false);
                            map[i][j]=0;
                            map[ni][nj]=0;
                        }
                    }
                }
            }

        }
    }

    static void dfs(int idx){ // 0~ 80
        if(idx == 81 ){
            if(!flag) {
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++) {
                        System.out.printf("%d", map[i][j]);
                    }
                    System.out.println();
                }
                flag = true;
            }
            return;
        }
        int x = idx/9;
        int y = idx%9;


        int nx,ny;
        if(map[x][y]!=0){
            dfs(idx+1);
        }else{
            for(int k=0;k<2;k++){
                nx = x + dx[k];
                ny = y + dy[k];
                if(0>nx || nx>=9 || 0>ny || ny>=9) continue;
                if(map[nx][ny]!=0) continue;
                for(int i=1;i<=9;i++){
                    for(int j=1;j<=9;j++){
                        if(i!=j && !block[i][j] && can(x,y,i) && can(nx,ny,j)){
                            map[x][y]=i;
                            map[nx][ny]=j;
                            block[i][j]=block[j][i]=true;
                            checking(x,y,i,true);
                            checking(nx,ny,j,true);
                            if(!flag) dfs(idx+1);
                            checking(x,y,i,false);
                            checking(nx,ny,j,false);
                            block[i][j]=block[j][i]=false;
                            map[x][y]=0;
                            map[nx][ny]=0;
                        }
                    }
                }
            }
        }

    }

    static boolean rangeCheck(int x,int y){
        if(0>x || x>=9 || 0>y || y>=9) return false;
        else return true;
    }

    static int toBox(int x,int y){
        return (x/3)*3+(y/3);
    }

    static boolean can(int x,int y,int num){
        return !c1[x][num] && !c2[y][num] && !c3[toBox(x,y)][num];
    }

    static void checking(int x,int y,int num,boolean what){
        c1[x][num] = what; // x행에 num이 있다.
        c2[y][num] = what; // y열에 num이 있다.
        c3[toBox(x,y)][num] = what; // 해당 박스에 num이 있다.
    }


}

 

속도 차이가 많이 난다.

 

dfs 문제를 확실하게 풀기 위해서는 방문할 수 있을지 명확하게 체크해야한다는 점이다.