[백준 2580] - [백트래킹] - 스도쿠

문제링크 : https://www.acmicpc.net/problem/2580

---

이문제는 백트래킹으로 접근 할 수 있는 문제이다.

예전에 풀었던 N-Queen 문제도 백트래킹이었는데 간단하게 설명하자면 

현재 인덱스에 값을 넣어보고 다음 탐색을 돌린다. 다시 현재 인덱스에는 값을 초기화 시킨다.

arr[y][x] = i;

backtracking(idx+1, cnt+1);

arr[y][x] = 0;

위에 소스처럼 백트래킹을 진행하는데 이렇게 하면 결국엔 다 초기화 되는거 아냐?? 하겠지만 잘 생각해보면 그렇지 않다.

최종 arr의 값은 당연히 초기 탐색할때의 값이 되겠지만 탐색을 하는 도중에 맞는 결과가 나왔을거고 

맞는 결과가 나왔을때 배열을 바로 출력을 했다. 

이해가 안된다면 백트래킹에 대한 설명 N-Queen 문제를 풀어보고 이문제를 접근하면 접근법이 보일것이라 생각한다.

2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen

문제를 푸는 방법은 값을 입력 받을때 0을 입력받으면 좌표를 배열에 add 한다.

배열에 add 한 좌표만 탐색하면 되기 때문에 list 에 add 한다.

그다음 1 부터 9까지 입력 가능한 수를 해당 좌표에 대입 시키고 

해당 좌표에 X 값이 위치했을때 성립하는지 같은 함수를 호출 해서 다음  탐색을 진행한다.

그렇게 된다면 전부 입력되는 한 순간이 나오고 그 때 배열을 출력 시키고 결과가 출력 됐으니 더이상 진행 하지 말라고 isEnd 라는 플래그를 true로 변경하여

더이상의 다른 불 필요한 탐색을 진행 못하게 막으면 된다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    public static final int size = 9;
    public static int[][] arr;
    
    public static List<int[]> list;
    public static boolean isEnd;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = null;
        
        arr = new int[size][size];
        list = new ArrayList<>();
        
        for(int i=0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            
            for(int j=0; j < size; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                
                if(arr[i][j] == 0) list.add(new int[] {i, j});
            }
        }
        // 입력 완료 
        backtracking(0, 0);
        
    }
    public static void backtracking(int idx, int cnt) {
        // 결과가 나왔다면 조회할 필요가 없다.
        if(isEnd) return;
        
        //빈칸에 입력된 cnt가 초기 zero 값의 cnt와 같다면 전부 입력이 된것.
        if(cnt == list.size()) {
            isEnd = true;
            print();
            return;
        }
        // 인덱스가 list크기를 넘어가면 종
        if(idx >= list.size()) return;
        
        int y = list.get(idx)[0];
        int x = list.get(idx)[1];
        
        // 1 부터 9 까지 입력 가능한 숫자 를 확인한다.
        for(int i=1; i<=9; i++) {
            // 해당 숫자가 가능하면 해당 좌표에 값을 입력하고 backtracking을 한다. 
            if(isAble(y, x, i)) {
                arr[y][x] = i;
                backtracking(idx+1, cnt+1);
                arr[y][x] = 0;
            }
        }
        
    }
    
    public static void print() {
        // 결과 출력
                StringBuilder sb = new StringBuilder();
                for(int i=0; i < size; i++) {
                    for(int j=0; j < size; j++) {
                        sb.append(arr[i][j] + " ");
                    }
                    sb.append("\n");
                }
                System.out.println(sb.toString());
    }
    public static boolean isAble(int y, int x, int v) {
        for(int i=0; i < size; i++) {
            // 가로가 유효한지 arr[y][x]의 값이 가로에 또 존재하면 안된다.
            if(arr[y][i] == v) return false;
            
            // 세로가 유효한지 arr[y][x]의 값이 세로에 또 존재하면 안된다.
            if(arr[i][x] == v) return false;
        }
        
        // 3*3이 유효한지
        int y_s = y/3 * 3;
        int x_s = x/3 * 3;
        for(int i = y_s; i < y_s+3; i++) {
            for(int j = x_s; j < x_s+3; j++) {
                if(arr[i][j] == v) return false;
            }
        }
        return true;
    }
}