[백준] 2580 스도쿠 (JAVA)

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

2580번: 스도쿠

풀이

문제 자체가 어렵지는 않으나 풀이방법에 대해서 조금 고민을 하여 푼 문제이다. 스도쿠의 룰은 잘 알다시피 가로세로 그리고 3*3이 되어있는 칸에서 중복을 허용하지 않는 선에서 수를 채워넣는 것이다. 그리하여 나는 81칸 전부를 차례대로 순회하며 만약 빈칸이 있다면 해당 칸에 들어갈수 있는 수를 찾은뒤 arr에 집어넣고 재귀적으로 호출해 나가며 풀이를 진행했다. 여기서 살짝 헷갈릴는 점은 적정값을 찾는 for문에서 전부 순회한후 마지막에 다시 0으로 집어넣고 return을 해주는데 이는 이전의 빈칸에 수를 집어 넣은것이 잘못돼 현재 칸 역시 알맞은 수를 집어 넣을수 없어 마치 아무일도 없었던것 처럼 0으로 되돌린다. 이를 조금더 쉽게 설명하면 만약 0으로 초기화 하지않은 채로 값이 들어간 상태로 자신을 호출한 함수로 돌아간다면 값은 여전히 넣어있는 상태로 돌아갈것이고 그렇다는 말은 향후 가로, 세로, 3*3을 범위로 하는 들어갈 수 있는 수를 조사할때 오류가 발생할수도 있기때문이다.

 

코드

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

class Main{

    public static int[][] arr = new int[10][10];
    static BufferedWriter bw;
    static BufferedReader br;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int i = 1; i <= 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= 9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        solve(1,1);

    }

    public static void solve(int x, int y) throws IOException {
       //가로 전부 찼을때
        if(y==10) {
            solve(x+1, 1);
            return;
        }

        //가로 세로 전부 찼을때
        if(x==10) {
            printfSudoku();
        }

        //빈칸일 경우 하나씩 집어넣어봄
        if(arr[x][y] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (check(x, y, i)) {
                    arr[x][y] = i;
                    solve(x, y + 1);
                }
            }
            arr[x][y] = 0; //처음으로 초기화 하는역할 --> for문 전부 돌았다고 해서 arr[x][y]에 있는 값이 정답이라는 보장 x
            return;
        }

        solve(x, y+1);
    }

    private static void printfSudoku() throws IOException {
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j < 10; j++) {
                bw.write(arr[i][j] + " ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        System.exit(0);
    }

    public static boolean check(int x, int y, int value){
        int upperLeft_x;
        int upperLeft_y;

        if(1<=x && x<=3) upperLeft_x=1;
        else if(4<=x && x<=6) upperLeft_x=4;
        else upperLeft_x = 7;

        if(1<=y && y<=3) upperLeft_y=1;
        else if(4<=y && y<=6) upperLeft_y=4;
        else upperLeft_y = 7;


        //row
        for (int i = 1; i <= 9; i++) {
            if(arr[x][i] == value)
                return false;
        }

        //col
        for (int i = 1; i <= 9; i++) {
            if(arr[i][y] == value)
                return false;
        }

        //3*3
        for (int i = upperLeft_x; i < upperLeft_x+3 ; i++) {
            for (int j = upperLeft_y; j < upperLeft_y+3; j++) {
                if(arr[i][j] == value)
                    return false;
            }
        }
        return true;
    }
}