백준 2239 스도쿠 Java [백트래킹, DFS]

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

2239번: 스도쿠

 

 

각 행과 열, 3x3 사각형의 방문 배열을 만들어 1 ~ 9 까지 중복없이 스도쿠 퍼즐을 채운다

3x3 사각형의 방문 배열의 경우 왼쪽 위에서부터 순서대로 배정했고,

행을 3으로 나눈 몫에 3을 곱하고, 열을 3으로 나눈 몫을 더해주면 해당 인덱스에 접근할 수 있다

사전식에서 가장 앞서는 경우를 출력해야하기 때문에 각 자리를 1부터 9까지 가능한 경우의 수를 구하고

끝까지 구해질 경우 탈출조건을 줘서 탐색을 멈추게 했다

 

import java.io.*;
import java.util.*;


public class Main {
    static int[][] puzzle;
    static boolean[][] row_vtd, col_vtd, squ_vtd;
    static boolean isFind;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        puzzle = new int[9][9];
        row_vtd = new boolean[9][10];
        col_vtd = new boolean[9][10];
        squ_vtd = new boolean[9][10];
        isFind = false;
        for (int i = 0; i < 9; i++) {
            puzzle[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (puzzle[i][j] != 0) {
                    setVtd(i, j, puzzle[i][j], true);
                }
            }
        }
        dfs(0, 0);
        for (int[] p : puzzle) {
            Arrays.stream(p).forEach(sb::append);
            sb.append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }

    static void dfs(int r, int c) {
        if (r == 8 && c == 9) {
            isFind = true;
            return;
        }
        if (c == 9) {
            r++;
            c %= 9;
        }
        if (puzzle[r][c] != 0) dfs(r, c + 1);
        else {
            for (int n = 1; n < 10; n++) {
                if (!isVtd(r, c, n)) {
                    setVtd(r, c, n,true);
                    dfs(r, c + 1);
                    if (isFind) {break;}
                    setVtd(r, c, n, false);
                };
            }
        }
    }

    static void setVtd(int r, int c, int n, boolean tf) {
        row_vtd[r][n] = tf;
        col_vtd[c][n] = tf;
        squ_vtd[(r/3)*3 + c/3][n] = tf;
        puzzle[r][c] = tf ? n : 0;
    }

    static boolean isVtd(int r, int c, int n) {
        return row_vtd[r][n] || col_vtd[c][n] || squ_vtd[(r/3)*3 + c/3][n];
    }
}

 

어디가 틀린지 모르고 dfs 메서드를 전체 디버깅하니까 틀린 지점 찾는데 너무 오래걸렸다

디버깅 포인트를 설정할 때 어디에 설정할지 좀 더 생각해봐야겠다