[백준] 2580 스토쿠(Java)

문제링크

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

문제분석

• 빈칸을 채우는 조건
  1. 가로줄과 세로줄에 대해 1~9 숫자는 한번씩 존재한다.
  2. 3x3 정사각형 안에도 1~9까지의 숫자가 한 번씩만 나타나야 한다.

입력

• 9 x 9 스토쿠 보드의 상태가 숫자로 입력된다.
• 빈칸은 '0'으로 표시된다.

출력

• 모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한줄에 9개씩 한 칸씩 띄어서 출력
• 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

풀이

1. 빈칸을 저장할 List를 선언한 뒤, 빈칸의 좌표를 List에 저장
2. 빈칸 List에 대해 DFS를 진행한다.
   • 1~9의 값을 넣고 조건을 check 한다.
     • 조건을 만족하면, 다음 빈칸으로 DFS진행한다.
     • 조건을 만족하지 않으면, 다른 숫자를 대입한 뒤 다시 검사한다.

개선점

• 조건을 검사하는 check 메서드
  - ch배열을 선언해 중복 확인 보다는, 파라미터에 test할 숫자를 같이 넘긴다.
  - 파라미터로 넘긴 숫자와 같은 숫자가 발견되면 false를 반환

코드

import java.util.*;

//좌표를 표현할 클래스 선언
class Point{
    int r, c;
    public Point(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main {
    //답이 존재하면 탐색을 종료하기 위한 변수
    static boolean answer = false;
    //빈 곳의 좌표를 저장할 List
    static ArrayList<Point> empty = new ArrayList<>();

    static int[][] board  = new int[9][9];

    //채워지는 빈칸이 3x3 정사각형에 대해 조건을 만족하는지 검사 시 사용
    //각 좌표에 대해 정사각형의 중간 좌표 반환
    static int[] getMiddle = {1, 1, 1, 4, 4, 4, 7, 7, 7};
    static int[] dr = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    static int[] dc = {-1, 0, 1, -1, 0, 1, -1, 0, 1};

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                board[i][j] = scanner.nextInt();

                //입력을 받는 중 빈 칸이면 list에 저장
                if(board[i][j]==0) empty.add(new Point(i, j));
            }
        }

        DFS(0);
    }
    static void DFS(int idx){
        if(answer==true) return ; //답이 이미 나왔다면, 탐색을 종료한다.
        if (idx == empty.size()) {
            answer = true;
            for(int i=0; i<9; i++){
                for(int j=0; j<9; j++){
                    System.out.print(board[i][j]+ " ");
                }
                System.out.println();
            }
            return ;
        }else{
            Point p = empty.get(idx);

            for(int j=1; j<=9; j++){
                board[p.r][p.c] = j;
                if(check(p.r, p.c)) //넣으려는 숫자가 조건을 만족한다면, 다음 빈칸에 대해 탐색한다.
                    DFS(idx+1);
                board[p.r][p.c] = 0;
            }
        }
    }
    //조건을 검사하는 메서드
    static boolean check(int r, int c){
        int[] ch1 = new int[10];
        int[] ch2 = new int[10];
        int[] ch3 = new int[10];

        //가로 세로 체크
        for(int i=0; i<9; i++){
            ch1[board[r][i]]++;
            ch2[board[i][c]]++;

            //같은 숫자가 나오면, false반환
            if(board[r][i]!=0)
                if(ch1[board[r][i]]==2) return false;
            if(board[i][c]!=0)
                if(ch2[board[i][c]]==2) return false;
        }

        //3x3 배열에 대한 조건 검사
        int middleR = getMiddle[r];
        int middleC = getMiddle[c];
        for(int i=0; i<9; i++){
            int nr = middleR + dr[i];
            int nc = middleC + dc[i];

            //같은 숫자가 나오면, false반환
            if(board[nr][nc]!=0) {
                ch3[board[nr][nc]]++;
                if (ch3[board[nr][nc]] == 2) return false;
            }
        }
        return true;
    }
}