정올 Q1824 스도쿠

정올 Q1824 스도쿠

문제 http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1097&sca=3030

백트레킹

 백트레킹이란 단어가 어렵게 느껴질 수 있지만 간단하게 말하면 모든 경우의 수를 다 확인하는 것으로 더 효율적인 방법으로 수행하는 것이다. 대표적 예로 DFS가 있다. (DFS, BFS는 차후 다룰 것이다.)

 단계별로 수행과정을 살펴보자.

1. 한 단계를 변화시킬 경우의 수를 찾는다.

2. 그 중 한개를 선택한다.(순서는 임의로 선택한다.)

3. 선택된 경우에 수에서 1 단계와 마찬가지로 가능한 경우의 수를 찾는다.

4. 위처럼 1,2번을 번갈아 가며 수행하고 중간에 경우의 수를 찾지 못하였을때 이전 단계로 돌아가 다음 경우의 수를 수행한다. 

여기서 4번처럼 목표에 도달하지 못하였을때 이전 단계로 돌아가는 과정 때문에 백트레킹이라는 이름이 붙혔다고 생각된다. 위 단계가 이해되지 않는 다면 DFS를 공부해보는 것을 추천한다. 

 

 그리디 알고리즘의 경우 현재에서 최선을 판단해 수행하지만 그것이 항상 답이라는 것을 보장받기 힘들다 이에 반해 백트래킹의 경우 모든 경우의 수를 수행한다는 점에서 최선의 답을 도출할 수 있지만 속도가 느리다는 단점이 있다.

고려사항

1. 가로선에 1~9까지 숫자중 하나만 들어간다.

2. 세로선에 1~9까지 숫자중 하나만 들어간다.

3. 사각형 안에 1~9까지 숫자중 하나만 들어간다.

4. 모두 0인경우가 존재할 수 있다.

문제 풀이

DFS는 스택을 사용하지만 스택 대신 재귀함수를 사용하여 문제를 해결하였다. 재귀도 스택도 같은 모양이니 편한데로 푸는것이 좋을듯 하다.

1. 입력을 받으며 빈곳의 위치를 배열에 저장한다. 

 위 맵의 경우 (0,0), (1,4), (1,7), (2,0)....이 저장될 것이다.

2. 배열에 저장된 순서대로 경우의 수를 확인한다.

2-1 (0,0)에 들어갈 수 있는 수를 확인한다. [1] 가능

2-2 (1,4)에 들어갈 수 있는 수를 확인한다. [3] 가능

.

.

.

3. 경우의 수가 2개 이상인경우 순서대로 실행한다.

4. 경우의 수가 없는 경우 이전단계로 돌아가 다음 경우의 수를 선택한다. Stack이나 재귀를 통해 가능

package week9;
import java.util.ArrayList;
import java.util.Scanner;
 
class Point{
    int x;
    int y;
    public Point(int x,int y) {
        // TODO Auto-generated constructor stub
        this.x = x;
        this.y = y;
    }
}
//스도쿠
public class Q1824{
     
     
    static ArrayList<Point> zeroP;
    static int[][] map;
    static boolean stop = false;
    public static void main(String[] args) {
        
        //빈곳을 저장하는 리스트
        zeroP = new ArrayList<>();
        
        //입력부
        Scanner sc = new Scanner(System.in);
        map = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                map[i][j] = sc.nextInt();
                if(map[i][j]==0){
                    zeroP.add(new Point(i, j));
                }
            }
        }
        //백트레킹 함수 시작, 파라미터는 빈곳 리스트의 index
        backTracking(0);
         
    }
    static public void backTracking(int num){
        //출력부 
        //빈곳의 마지막까지 도착하였을시, 즉 빈곳이 모두 채워졌을시 종료
        if(num==zeroP.size()){
            //이후 더이상 경우의 수가 검사되지 않도록 하는 flag
            stop = true;
            for(int a=0;a<9;a++){
                for(int b=0;b<9;b++){
                    System.out.print(map[a][b]+" ");
                }
                System.out.println();
            }
            return;
        }
        
        
        Point p = zeroP.get(num);
        //num 위치에 들어갈수 있는 숫자목록을 불러옴
        ArrayList<Integer> list = getNum(p.x,p.y);
        
        //경우의 수가 존재 하지 않을시
        if(list.size()==0){
            return;
        }
         
        for(int i=0;i<list.size();i++){
            map[p.x][p.y] = list.get(i);
            if(stop){
                return;
            }else{
                //다음 단계로 이동
                backTracking(num+1);
            }
        }
        //이전 단계로 돌아갈시 반드시 현재위치를 다시 빈곳으로 
        //변환하여야 한다.
        map[p.x][p.y] = 0;
    }
 
    //가능한 숫자를 얻어옴
    static ArrayList<Integer> getNum(int x, int y) {
        boolean flag = true;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            if(lineXCheck(x, i) && lineYCheck(y,i) && recCheck(x, y, i)){
                list.add(i);
            }
        }
         
        return list;
    }
    //가로선을 검사하여 가능한 숫자인지 확인
    static boolean lineXCheck(int lineX, int input){
        for (int i = 0; i < 9; i++) {
            if(map[lineX][i]==input){
                return false;
            }
        }
        return true;
    }
    //세로선을 검사하여 가능한 숫자인지 확인
    static boolean lineYCheck(int lineY, int input){
        for (int i = 0; i < 9; i++) {
            if(map[i][lineY]==input){
                return false;
            }
        }
        return true;
    }
    //포함된 사각형을 검사하여 가능한 숫자인지 확인
    static boolean recCheck(int x, int y, int input){
        int startX = x/3*3;
        int startY = y/3*3;
        for(int i =startX;i<startX+3;i++){
            for(int j =startY;j<startY+3;j++){
                if(map[i][j]==input){
                    return false;
                }
            }
        }
        return true;
    }
 
}