[백준 풀이] 백준 2580 "스도쿠"

"삽질의 연속"
https://www.acmicpc.net/problem/2580
(대충 삽질한거 털어놓는글)
어떤 칸에 들어갈 수 있는 수를 찾는것 부터 꼬인것 같다. 나는 가로 세로 사각형 안에 없는 수를 찾아내서 그것을 배열로 만들어서 한번에 테스트해볼 생각이였는데 너무 안되어서 옛날에 써놨던 글을 봤더니 그게 아니라 possible 함수를 호출하기 전에 먼저 반복문으로 1~9를 돌려서 그 숫자 하나하나마다 가능 여부를 따지는거였다. 애초에 이 부분부터 잘못되었고 또 하나 잘못한 점은 백트래킹만으로(Nqueen처럼) 풀어볼려했는데 그게 아니라 dfs를 이용하는거였다. 어쩐지 이상하다 했는데 백트래킹에 이 문제가 있는 이유는 DFS를 실행하다가 완전히 탐색하는것이 아니고 백트래킹적 성격이 있기 때문인것 같습니다. DFS와 백트래킹은 정말 가까운 관계인듯 하네요 백트래킹으로 푸는 법은 있는데 너무 복잡해져서 DFS로 푸는것 같다. DFS를 써보자..

그래서 결론을 말하면 DFS를 돌리면서 0이 있는 인덱스만 따로 모아서 리스트를 만들고 cnt를 하나씩 증가시키면서 재귀호출하면서 그 리스트를 순회합니다. 그 안에서 숫자를 1부터 9까지 반복문을 돌려서 하나하나 되는지 여부를 확인하는게 풀이 방법이였습니다.
이렇게 풀린다는걸 안 이상 코드는 쉽게 작성했네요.

import java.sql.Array;
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;

public class Main {
    static int[][] board = new int[9][9];
    static int[][] answer = new int[9][9];
    static ArrayList<int[]> zeros = new ArrayList<>();
    static boolean Feasible(int x, int y, int n) {
        for(int i = 0;i < 9;i++) {
            if(board[x][i] == n) {
                return false;
            }
        }
        for(int i = 0;i < 9;i++) {
            if(board[i][y] == n) {
                return false;
            }
        }
        for(int i = ((int) x / 3) * 3;i < ((int) x / 3) * 3 + 3;i++) {
            for(int j = ((int) y / 3) * 3;j < ((int) y / 3) * 3 + 3;j++) {
                if(board[i][j] == n) {
                    return false;
                }
            }
        }
        return true;
    }
    static void dfs(int cnt) {
        if(cnt == zeros.size()) {
            for(int i = 0;i < 9;i++) {
                for(int j = 0;j < 9;j++) {
                    answer[i][j] = board[i][j];
                }
            }
            return;
        }
        int x = zeros.get(cnt)[0];
        int y = zeros.get(cnt)[1];
        for (int i = 1; i < 10; i++) {
            if (Feasible(x, y, i)) {
                board[x][y] = i;
                dfs(cnt + 1);
                board[x][y] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for(int i = 0;i < 9;i++) {
            String[] input1 = in.nextLine().split(" ");
            for (int j = 0; j < 9; j++) {
                board[i][j] = Integer.valueOf(input1[j]);
                if(board[i][j] == 0) {
                    zeros.add(new int[]{i, j});
                }
            }
        }
        dfs(0);
        StringBuilder output = new StringBuilder();
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                output.append(answer[i][j]);
                output.append(" ");
            }
            output.append("\n");
        }
        System.out.print(output);
    }
}

dfs 관련 문제들은 몇번 더 풀어봐야 감이 잡힐 것 같습니다.