BOJ 2580) 스도쿠

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

2580번: 스도쿠

문제

접근

 (처음에는 답이 정해진 스도쿠의 경우만 생각해서

1. 행을 검사하여 1개의 0이 존재한다면 정해진 숫자 삽입
2. 열을 검사하여 1개의 0이 존재한다면 정해진 숫자 삽입
3. 3x3크기의 행렬을 검사하여 1개의 0이 존재한다면 정해진 숫자 삽입

과 같이 반복문을 이용하여 삽입하는 코드를 짜고, 왜 이게 백트래킹 문제인지 의아했지만)

출력조건에서 나와있듯이 '스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.'라고 하여, 모든 칸이 0으로 채워진 경우에도 결과를 출력해내야 하는 문제였다.

 

 그렇다면 '답이 한 개 이상 존재하는 임의의 주어진 입력값에 대해서 가능한 하나 이상의 답을 출력하는 것'이 목표이고, 이전의 값에 의해 다음 값이 무조건 확정되어서 점화식을 구할 수도 없고, 답을 구하기 이전에는 빈칸에 들어갈 값을 확정할 수도 없으므로 각 빈칸들에 들어갈 모든 경우들에 대해서 dfs를 이용하여 풀면 되겠다고 생각했다.

 

 먼저 9x9스도쿠판을 표현하기 위해 2차원 배열 arr을 사용하겠다. 또한 직관적인 인덱스 표기를 위해서 arr[1][1]을 1행 1열로 놓고 코드를 작성하였다.

 비록 틀린 풀이의 일부이기는 했지만, 그것에서 알 수 있듯 스도쿠의 규칙은

0. 좌표가 빈 칸(0)이 아니라면 값을 삽입할 수 없다.
1. 같은 행에 있는 원소 중에 중복된 수가 없다.
2. 같은 열에 있는 원소 중에 중복된 수가 없다.
3. 해당 원소가 속한 3x3행렬 속에서 중복된 수가 없다

의 3가지 조건을 만족해야 하고, 이 조건이 (주어진 좌표에 주어진 수)가 들어갈 수 있는지 판별하는 유망함수가 된다. 이때 좌표와 수는 매개변수로 넘겼다.

    private static boolean isPromising(int[][] arr, int x, int y, int value) { //value를 하나하나 넣어서 검사
        if(arr[x][y]!=0) return false;

        //같은 행에 동일한 값이 있는지 검사
        for(int i=1; i<=9; i++) {
            if(arr[x][i]==value)
                return false;
        }

        //같은 열에 동일한 값이 있는지 검사
        for(int i=1; i<=9; i++) {
            if(arr[i][y]==value)
                return false;
        }

        //3x3크기 내에 동일한 값이 있는지 검사
        for(int i=(x-1)/3*3+1; i<=(x-1)/3*3+1+2; i++)
            for(int j=(y-1)/3*3+1; j<=(y-1)/3*3+1+2; j++)
                if(arr[i][j]==value)
                    return false;

        //모든 조건에 안걸리면 유망
        return true;
    }

 

이제 유망함수를 만들었으니, 배열의 모든 원소에 대해서 검사하는 dfs함수를 만들어주자.

private static void sudoku(int[][] arr, int x, int y) throws IOException {
        
}

 

먼저 dfs함수에는 행번호와 열번호를 매개변수로 넘겨서 해당 번호에 대해 유망성을 검사하고, 조건에 따라 재귀호출이 가능하도록 만들었다.

 

또한 행렬의 전체 원소를 대상으로 검사하도록 했으므로, arr[1][1]부터 arr[1][9]까지, arr[2][1]부터 [2][9]까지... arr[9][1]부터 arr[9][9]까지 열번호를 증가시키면서 행마다 9개의 원소를 검사하면 될것이다. 단,  y좌표, 즉 n행 9열을 검사했을 경우에는 다음에 n행 10열이 아니라 n+1행 1열이 와야 한다.

 

private static void sudoku(int[][] arr, int x, int y) throws IOException {
        if(y==9) { //x행 9열을 검사했을 경우
            for (int i = 1; i <= 9; i++) {
                if (isPromising(arr, x, y, i)) {
                    arr[x][y] = i;
                    sudoku(arr, x + 1, 1); // 다음에는 (x+1)행 1열을 검사
                    arr[x][y] = 0;
                }
            }
            if(arr[x][y]==0)
                return;
            sudoku(arr, x + 1, 1);
        }
        else {
            for (int i = 1; i <= 9; i++) {
                if (isPromising(arr, x, y, i)) {
                    arr[x][y] = i;
                    sudoku(arr, x, y + 1); //그밖의 경우 x행 y+1열을 검사
                    arr[x][y] = 0;
                }
            }
            if(arr[x][y]==0)
                return;
            sudoku(arr, x, y+1);
        }
    }

여기에 종료조건은 9행 9열까지 모든 좌표를 검사한 후 'n행 9열을 검사했을 때의 조건'에 따라 다음에 재귀호출의 인자로 넘어갈 (9+1)행 1열을 종료조건으로 받아주면 되므로,

        if(x==10) {
            for (int i = 1; i <= 9; i++) {
                for (int j = 1; j <= 9; j++)
                    bw.write(arr[i][j] + " ");
                bw.write("\n");
            }
            bw.flush();
            bw.close();
            System.exit(0); //시스템 종료
        }

이와 같이 함수를 작성하였다. 이때 break;로 재귀호출을 끝내고 상태공간트리의 전 노드로 돌아가는 것이 아니라, '스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.'는 문제 조건에 따라 출력 후 시스템을 종료해주어야 한다.

 

 

코드 전문

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

public class Main {

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //가로줄 검사, 세로줄 검사, 3x3 검사 > 유망 조건
    public static void main(String[] args) throws IOException {

        String str;
        int[][] arr = new int[10][10];


        //2차원 배열에 저장
        for (int i = 1; i <= 9; i++) {
            str = br.readLine();
            StringTokenizer st = new StringTokenizer(str);
            for (int j = 1; j <= 9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        sudoku(arr, 1, 1);

    }

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


        if(y==9) {
            for (int i = 1; i <= 9; i++) {
                if (arr[x][y]==0 && isPromising(arr, x, y, i)) {
                    arr[x][y] = i;
                    sudoku(arr, x + 1, 1);
                    arr[x][y] = 0;
                }
            }
            if(arr[x][y]==0)
                return;
            sudoku(arr, x + 1, 1);  //원래 배열이 0이 아니었으면 넘어가기
        }
        else {
            for (int i = 1; i <= 9; i++) {
                if (arr[x][y]==0 && isPromising(arr, x, y, i)) {
                    arr[x][y] = i;
                    sudoku(arr, x, y + 1);
                    arr[x][y] = 0;
                }
            }
            if(arr[x][y]==0)
                return;
            sudoku(arr, x, y+1);
        }
    }


    private static boolean isPromising(int[][] arr, int x, int y, int value) { //value를 하나하나 넣어서 검사
        //if(arr[x][y]!=0) return false;

        //같은 행에 동일한 값이 있는지 검사
        for(int i=1; i<=9; i++) {
            if(arr[x][i]==value)
                return false;
        }

        //같은 열에 동일한 값이 있는지 검사
        for(int i=1; i<=9; i++) {
            if(arr[i][y]==value)
                return false;
        }

        //3x3크기 내에 동일한 값이 있는지 검사
        for(int i=(x-1)/3*3+1; i<=(x-1)/3*3+1+2; i++)
            for(int j=(y-1)/3*3+1; j<=(y-1)/3*3+1+2; j++)
                if(arr[i][j]==value)
                    return false;

        //모든 조건에 안걸리면 유망
        return true;
    }
}

 

 

실행시간 관련 고민중

실행시간을 더 줄이려면 어떻게 해야할까?

찾아보니 최소 400ms에서 1100ms까지 있던데, 내 코드는 800ms정도 나온다.

 

1. arr[x][y]가 0이 아니면 유망함수를 호출조차 하지 않게끔 아예 if문에 추가해보았다

> 유의미한 차이는 아닌것 같다.

2. 유망함수에서 중복된 사칙연산을 변수로 저장해보았다.

> 유의미한 차이는 아닌것 같다.

3. 배열을 매개변수가 아닌 static변수로 만들어보았다.

> 유의미한 차이는 아닌것 같다.

4. BufferedWriter 대신 StringBuilder를 이용한 출력을 해보았다.

> 700ms 후반대까지 줄어들긴하는데 더 줄이고 싶다.

5. dfs함수를 수정하였다.

> 400ms대로 수행시간이 감소했다.

 

private static void sudoku(int x, int y) {
        //개행해야 할 경우
        if(y==10) {
            sudoku(x+1, 1);
            return;
        }

        if(x==10) {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= 9; i++) {
                for (int j = 1; j <= 9; j++)
                    sb.append(arr[i][j]).append(' ');
                sb.append('\n');
            }
            System.out.println(sb);
            System.exit(0);
        }

        if(arr[x][y]==0) {
            for (int i = 1; i <= 9; i++) {
                if (isPromising(x, y, i)) {
                    arr[x][y] = i;
                    sudoku(x, y + 1);
                    arr[x][y] = 0;
                }
            }
            return;
        }


        sudoku(x, y+1);
    }

1. 원래는 y가 9(마지막)인경우의 분기를 따로 만들었는데, 여기서는 1~9까지 동일하게 처리하고 10일때 처리해주는 조건문만 만들었다.

> 간단하게 열이 10이면 다음행 1열 호출, 행이 10이면 출력후 종료

2. 모든 if문에서 리턴되거나 시스템 종료되지 않으면 그냥 넘어가는 코드를 공유하도록 빼놓음.

> 크게 런타임에 영향줄거같진않은데 ㅠ

 

 

로직의 큰 차이도 없는것같은데 런타임이 두배 가까이 차이나는 이유를 모르겠다. 열이 9일때 처리하는것과 10일때 처리해주는 차이와 열과 행의 순서 차이일뿐인데!

> 문제의 채점 데이터가 편향되어있다고 한다. 마지막 열에서 조건문에 걸리는 케이스가 많이 반복된다면 그럴수 있을지도?