[백준 알고리즘 - 백트래킹] 스도쿠

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

소요시간: 3시간 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 삼성 가고파요 제발

풀이입니다 참고만 해주세요 알고리즘 초보자입니다.

colMaps[i][j] ====> i행에 j라는 숫자가 있다면 1, 없다면 0

rowMaps[i][j] ====> i열에 j라는 숫자가 있다면 1, 없다면 0

groupMaps[i][j] ====> i그룹에에 j라는 숫자가 있다면 1, 없다면 0 (그룹의 인덱스의 경우 i = 3*(x좌표/3) + y좌표/3 으로 표현해 줬다.)

N-Queen 문제와 마찬가지로, 다음 노드 방문 여부를 판단(isPromising)해야 한다.(백트레킹)

그런데, 모든 행, 열, 그룹을 탐색하기에는 시간이 너무 오래 걸린다.

그래서 공통된 행, 열, 그룹과 숫자를 Index로 활용하면 탐색 시간을 줄일 수 있다. 

Ex) 1행에 2라는 숫자를 탐색하려면 maps[1][i]==2 를 i를 0부터 8까지 탐색해야 하는데 굳이 공통된 1행을 9번이나 탐색할 필요가 없다. 위 방법을 이용하여 공통된 행을 배열로 표현해주면 col[1][2]==1 로 한번만 탐색하면 된다.

이해가 안간다면 삼성 EA에 N-Queen을 다시 풀어볼 것!

테스트케이스는

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

로 돌려봤다.

중간에 자꾸 틀려서 확인해보니 return을 잘못 줬다. DFS를 빠져나오는 부분을 유심히 살펴보자..!

import java.util.Scanner;
 
class Main {
    static int N,K,TC,answer, index, length;
    static int[][] maps, colMaps, rowMaps, groupMaps;
    static int[] xStack, yStack;
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = 9;
        maps = new int[n+1][n+1];
        colMaps = new int[n+1][n+1];
        rowMaps = new int[n+1][n+1];
        groupMaps = new int[n+1][n+1];
        xStack = new int[n*n]; // 0을 저장할 x, y 좌표
        yStack = new int[n*n];
        index = 0; // 스택을 가르킬 인덱스
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                maps[i][j] = sc.nextInt();
                if(maps[i][j]!=0){
                    colMaps[i][maps[i][j]] = 1;
                    rowMaps[j][maps[i][j]] = 1;
                    groupMaps[(3*(i/3)+j/3)][maps[i][j]] = 1;
                }
                else{
                    xStack[index]=i;
                    yStack[index]=j;
                    index++;
                }
            }
        }
        length = index;
        
        index = 0;
        int x = xStack[index];
        int y = yStack[index];
        
        for(int num=1;num<=9;num++){
            if(isPromising(x,y,num)){
                if(dfs(x,y,num))
                    break;
            }
        }
        
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                System.out.print(maps[i][j]+" ");
            }
            System.out.println();
        }
    
        
    }
 
     static boolean dfs(int x, int y, int num) {
 
            maps[x][y]=num;
            colMaps[x][num]=1;
            rowMaps[y][num]=1;
            groupMaps[3*(x/3)+y/3][num]=1;
            
             index++;
             
             if(index==length){
                 return true;
             }
 
            
            int nextX = 0; int nextY=0;
            
            nextX = xStack[index];
            nextY = yStack[index];
            
            for(int nextNum=1;nextNum<=9;nextNum++){
                if(isPromising(nextX,nextY,nextNum)){
                    if(dfs(nextX,nextY,nextNum))
                        return true;
                }
            }
            
            index--;
            colMaps[x][num]=0;
            rowMaps[y][num]=0;
            groupMaps[3*(x/3)+y/3][num]=0;
            
            return false;
        
    }
 
        static boolean isPromising(int i, int j,int num) {
            if(colMaps[i][num]!=1 && rowMaps[j][num]!=1 && groupMaps[3*(i/3)+j/3][num]!=1){
                return true;
            }
            else    
                return false;
    }
}