백준 2239번 스토쿠 [JAVA]

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

 

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

 

 

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

 

출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main_BJ_2239_스토쿠 {
    static int N=9;
    static int [][] puzzle;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        puzzle = new int [N][N];
        
        for(int i=0;i<N;i++) {
            String str = br.readLine();
            for(int j=0;j<N;j++) {
                puzzle[i][j]=str.charAt(j)-48;
            }
        }
        
        input(0,0);
        
    }
    
    public static void input(int x, int y) {
        int nx = x, ny = y+1;
        if(ny==9) {
            nx = x+1;
            ny=0;
        }
        
        
        if(x==9) { //탐색 끝
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    System.out.print(puzzle[i][j]);
                }
                System.out.println();
            }
            System.exit(0);
        }
        
        
        if(puzzle[x][y]!=0) {
            input(nx,ny);
        }
        else {
            
            for(int i=1;i<=9;i++) {
                
                if(col(y,i) || row(x,i) || (rectangle(x, y, i))) continue;
                
                puzzle[x][y] = i;
                
                input(nx,ny);
                
                puzzle[x][y]=0;
                
            }
        }
    }
    
    
    public static boolean col(int y , int value) { //세로검사
        
        for(int i=0;i<N;i++) {
            if(puzzle[i][y]==value) return true;
        }
        return false;
        
    }
    
    public static boolean row(int x, int value) { //가로검사
        
        for(int i=0;i<N;i++) {
            if(puzzle[x][i]==value) return true;
        }
        return false;
        
    }
    
    public static boolean rectangle(int x, int y, int value) { // 3x3 배열검사
        
        int X = (x/3)*3;
        int Y = (y/3)*3;
        
        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++) {
                if(puzzle[X+i][Y+j]==value) return true;
            }
        }
        return false;
        
    }
 
}

 

풀이방법

스토쿠를 완성시키기 위해 빈 칸을 채우는 문제였습니다.

 

저는 (0,0)부터 스토쿠 오른쪽 아래인 (8,8)까지 차례대로 진행하였습니다.

해당 위치가 0일경우에는 숫자 1~9를 넣어보면서 가로/세로/3*3 검사를 통해 해당 위치에 들어갈 수 있는 숫자를 넣어주었습니다.

x좌표가 9일 경우 즉 모든 스토쿠의 빈칸을 채웠을 경우, 해당 스토쿠를 출력해주었습니다.