문제 개요

스도쿠

백트래킹 문제
dfs를 통해서 들어갈 수 있는 수를 무작위로 넣어준다

여기에서 들어갈 수 있는 수는 1 ~ 9 로 다른 수와 중복이 될 수 있기 때문에
중복조합으로 구현했다.

가능한 수를 찾는것과 동시에 스도쿠를 만족할 수 있는지 조건문을 통해 확인한 뒤 수를 넣어준다
이 부분이 백트래킹 조건이 된다.

중간에 내가 잘못 체크한 부분을 써놓자면.

1.1-9까지 true로 체크해가면서 boolean 배열을 사용하려고 함 -> 이건,그냥 내가 넣는 value랑 똑같은게 있는지 확인만 하면 쉽게 갈 수 있다
2.중복조합으로 빈칸을 완성한 다음 스도쿠 여부를 찾으려고 했다 -> 수 하나하나를 넣어보면서 안되는 경우를 빼주는 것이 시간복잡도 면에서 효율적이다. 왜냐하면 코드가 재귀 형식으로 구현되어있기 때문에 더 깊이 들어가기 전에 백트래킹으로 빼주기 때문이다. 즉,스도쿠가 맞는지를 확인하기 위해서 무조건 모든 0 인 공간을 채워야 한다면 재귀를 더 많이 돌아야 한다.

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * dfs + 조건 구현 문제
 * dfs를 통해서, 빈칸에 들어갈 수 있는 숫자를 찾은 다음 조건에 맞는지 확인한다.
 * 이 문제가 백트래킹에 해당하는 이유는 스도쿠가 되는 조건을 통해 필터링하기 때문이다
 * @see
 * https://www.acmicpc.net/problem/2580
 * @since 2023-10-26
 **/
public class 스도쿠 {
    static class Point{
        int x,y,value;

        public Point(int x, int y,int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }
    static int[][] map;
    static ArrayList<Point> points;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        map = new int[9][9];
        points = new ArrayList<>();
        for(int i=0;i<9;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<9;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 0) points.add(new Point(i,j,0));
            }
        }
        dfs(0);
    }

    static void dfs(int depth){
        if(depth == points.size()){
            //0의 개수만큼 루프를 돌았다면
            //스도쿠 확인
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    sb.append(map[i][j]).append(" ");
                }
                sb.append("\n");
            }
            System.out.print(sb);
            System.exit(0);

        }
        Point p = points.get(depth);
        for(int i=1;i<10;i++) {
            if(validation(new Point(p.x,p.y,i))) {
                map[p.x][p.y] = i;
                dfs(depth + 1);
                map[p.x][p.y] = 0;
            }
        }
    }

    static boolean validation(Point point){
        int col = point.x;
        int row = point.y;
        int value = point.value;

        //해당 지점이 유효한지 테스트한다

        for(int i=0;i<9;i++){
            if(map[col][i] == value) return false;
        }

        for(int i=0;i<9;i++){
            if(map[i][row] == value) return false;
        }

        int nCol = (col / 3) * 3;
        int nRow = (row / 3) * 3;

        for(int i=nCol;i<nCol+3;i++){
            for(int j=nRow;j<nRow+3;j++){
                if(map[i][j] == value) return false;
            }
        }

        return true;
    }
}