백준 2580 스도쿠 Java 풀이

문제

9x9 스도쿠 판이 입력으로 주어지면 이 이 스도쿠 판을 다음의 규칙에 따라 완성해서 출력하는 문제이다. *(반드시 완성이 가능한 스도쿠만 입력으로 주어진다.)

(1) 각각의 가로줄과 세로줄에 1부터 9까지의 숫자가 한번씩 나타나야한다.

(2) 3x3 정사각형 안에도 1부터 9까지의 숫자가 한번씩 나타나야한다.

접근

이렇게 풀면 되지 않을까?

(1) 판을 순회하면서 1 ~ 9 까지의 숫자가 해당 판에 가로조건, 세로조건, 3x3 조건을 충족하면 놓는다.

(2) 그 다음으로 이동한다.

(3) 만약 모든 숫자에 대해서 가로조건, 세로조건, 3x3 조건을 충족하지 못한다면 가능한 최소한의 경우의 수로 롤백한다.

 

그리고 이러한 문제 풀이는 백트래킹의 일종인 깊이우선 탐색을 통해 풀 수 있다.

 

풀이

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

public class Main {

    static int N = 9;
    static int[][] board = new int[N][N];
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        placeNumberAt(0);
    }

    static void placeNumberAt(int pos) {
        if (pos == N*N) { // 무조건 완성이 가능한 스도쿠라고 했으니 pos == N*N 조건에 닿음.
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    sb.append(board[i][j]).append(" ");
                }
                sb.append("\n");
            }
            System.out.println(sb);
            System.exit(0);
        }

        int x = pos / N;
        int y = pos % N;

        if (board[x][y] != 0) { // 이미 숫자가 놓여져 있다면 다음 숫자로 넘어감
            placeNumberAt(pos+1);
        } else { // 숫자가 놓여져 있지 않다면 하나씩 대입해봄
            for (int number = 1; number < N+1; number++) {
                if (isPlaceableAt(x, y, number)) { // 대입이 가능하다면 대입함
                    board[x][y] = number;
                    placeNumberAt(pos+1);
                    board[x][y] = 0; // 백트래킹, 초기화, 이 단계로 넘어왔다는건 해당 숫자를 넣고 a 번 뒤에 불가능해졌다는 거임, 따라서 숫자를 놓았다는 사실을 rollback 함
                }
                // 모든 숫자가 대입이 불가능하다면 자연스럽게 종료
            }
        }
    }

    static boolean isPlaceableAt(int x, int y, int number) {
        // 가로조건 판단(같은 숫자가 있으면 안된다.)
        for (int i = 0; i < N; i++) {
            if (board[x][i] == number) {return false;}
        }
        // 세로조건 판단(같은 숫자가 있으면 안된다.)
        for (int i = 0; i < N; i++) {
            if (board[i][y] == number) {return false;}
        }

        // 3*3 내부 조건 판단
        int x33Start = (x / 3) * 3;
        int y33Start = (y / 3) * 3;

        for (int i = x33Start; i < x33Start+3; i++) {
            for (int j = y33Start; j < y33Start+3; j++) {
                if (board[i][j] == number) {return false;}
            }
        }
        return true;
    }
}

 

백준 문제 출처: https://www.acmicpc.net/problem/2580