[백준2580번] 스도쿠

문제

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

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

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

출력

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

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

예제 입력 1 복사

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

예제 출력 1 복사

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

나의 풀이

n-Queen문제와 비슷하게 백트래킹으로 풀어보았다. 2차원 배열에 입력 받는 빈 칸이 있는 스도쿠를 저장하고 (0,0)부터 시작을 하면서 '0'값을 가지고 있는 즉, 빈 칸을 만나면 1부터 9까지 차례대로 넣어보며 유망한지를 체크하고 유망하면 다음 값으로 넘어가고 그렇지 않으면 뒤로 돌아가는 방식으로 풀이했다. 여기서 유망한지는 문제에서도 알려주었듯이 가로줄,세로줄,3x3에 1부터9가 다 있어야 한다. 즉, 반복되는 수가 있으면 안된다. 가로와 세로를 확인하는 것은 어렵지 않지만 3x3에서 실수를 할 수도 있었다. 2차원 배열을 N+1로 할당을 하여 0번 index를 비워서 저장을 하게 되면 3x3 사각형에서 처리가 쉽지 않았다. 따라서 그냥 0부터8까지의 index를 사용한다면 해당 index를 3으로 나누고 다시 3을 곱하면 0, 3, 6 이 세가지 값만 나오게 되므로 쉽게 처리가 가능했다.

그리고 문제에서 해결법이 여러개일때에는 한가지만 출력하라고 알려주었다. 밑의 코드에서 print() 메서드에서 프로그램 종료를 해주지 않는다면 위의 예제 입력에서는 하나만 나오지만 모두 0으로 채워진 값을 넣으면 아주 많은 해결책이 출력되는 것을 볼 수 있다. 그래서 나는 print()메서드에 System.exit(0)을 넣어 최초에 나오는 하나만 출력이 되게끔 해주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 2580번 스도쿠
 */
public class Baeckjun2580 {

    static int N = 9;
    static int[][] panel;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        panel = new int[N][N];

        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++) {
                panel[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        sdoku(0,0);

    }

    static void print() {
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                System.out.print(panel[i][j]);
                System.out.print(' ');
            }
            System.out.println();
        }
        // 여러 경우가 print될 경우를 대비하기 위해 한번 출력하면 프로그램 종료!
        System.exit(0);
    }

    static void sdoku(int r, int c) {
        if (panel[r][c]==0) {
            for (int num=1; num<=9; num++) {
                panel[r][c] = num;
                if (promising(r, c)) {
                    if (r==N-1 && c==N-1) print();
                    else if (r == N - 1) sdoku(r, c + 1);
                    else if (c == N - 1) sdoku(r + 1, 0);
                    else sdoku(r, c + 1);
                }
                panel[r][c] = 0;
            }
        } else {
            if (r==N-1 && c==N-1) print();
            else if (r == N - 1) sdoku(r, c + 1);
            else if (c == N - 1) sdoku(r + 1, 0);
            else sdoku(r, c + 1);
        }
    }

    static boolean promising(int r, int c) {
        // 세로
        for (int i=0; i<N; i++) {
            if (i==r) continue;
            if (panel[r][c] == panel[i][c]) return false;
        }
        // 가로
        for (int i=0; i<N; i++) {
            if (i==c) continue;
            if (panel[r][c] == panel[r][i]) return false;
        }
        // 3*3
        for (int i=(r/3)*3; i<(r/3)*3+3; i++) {
            for (int j=(c/3)*3; j<(c/3)*3+3; j++) {
                if (i==r && j==c) continue;
                if (panel[r][c] == panel[i][j]) return false;
            }
        }
        return true;
    }

}