백준 2580 스도쿠 java 풀이

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

 

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

문제 풀이

 스도쿠의 규칙은 가로, 세로, 3*3 박스 내에서 같은 값이 없는 1~9 숫자를 넣어서 전체 표를 완성하는 놀이. 여기서 공백이 있는 칸(문제에서는 0)을 가로 세로 박스내에서 체크해서 넣을 수 있는 값을 넣고 다음 빈칸으로 이동하기를 반복 전체 표가 완성되면 출력하도록 했다. DFS 방식으로 접근해서 문제를 풀었는데, 풀고나서 든 생각은 빈칸을 전부 큐에 넣어놓고 하나씩 꺼내가며 가로 세로 3*3박스 내에서 일치하는 값이 없는 확정적인 빈칸에만 값을 넣고, 불확실한 값(여러 값을 넣을 수 있는 경우) 에는 다시 큐에 집에넣는 방식으로 해도 문제가 풀릴거 같다. 어떤 풀이가 더 빠를지는 구현 후 비교해보아야 겠는데, 생각보다 이 코드도 작성하는데 시간이 많이 걸렸어서 큐를 사용한 방식은 해보고 수정하기로..

 

코드

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

public class Main {
    public static int[][] arr = new int[10][10];
    public static List<Point> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        for(int i=1; i<=9; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]==0) {
                    list.add(new Point(i,j));
                }
            }
        }
        
        recur(0);
        
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<10; i++) {
            for(int j=1; j<10; j++) {
                sb.append(arr[i][j]+" ");
            }
            sb.append("\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
    }
    
    public static boolean recur(int idx) {
        if(idx==list.size()) {
            return true;
        }
        Point temp = list.get(idx);
        for(int i=1; i<10; i++) {
            if(!checkMap(temp.y, temp.x,i))
                continue;
            arr[temp.y][temp.x] = i;
            boolean flag = recur(idx+1);
            if(flag) return true;
            arr[temp.y][temp.x] = 0;
        }
        
        return false;
    }
    
    public static boolean checkMap(int y, int x, int num) {
        for(int i =1; i<10; i++) {
            if(arr[y][i]==num || arr[i][x]==num)
                return false;
        }
        
        for(int i = ((y-1)/3)*3+1; i<((y-1)/3)*3+4; i++) {
            for(int j = ((x-1)/3)*3+1; j<((x-1)/3)*3+4; j++) {
                if(arr[i][j]==num)
                    return false;
            }
        }
        return true;
    }  
}

class Point {
    int x;
    int y;
    Point(int y, int x) {
        this.x = x;
        this.y = y;
    }
}