[백준 - 2580] 스도쿠 - Java

문제 설명

 

2580번: 스도쿠

 

접근 방법

해당 문제는 백트래킹을 이용하여 해결할 수 있었습니다.

 

우선 주어진 스도쿠 데이터에서 빈 칸(0)의 개수를 카운팅해서 백트래킹 시 최대 depth(깊이)로 설정했습니다. 이후 9 * 9 스도쿠 판 좌표 (1, 1) 지점부터 마지막 (9, 9) 지점까지 순차적으로 백트래킹하면서 빈 칸을 채워나갔습니다.

 

해당 빈 칸을 채울 때는 우선 해당 빈칸에 나올 수 있는 숫자 목록을 구해내도록 했습니다. 이때 해당 빈 칸에 나올 수 있는 숫자들은 해당 빈 칸의 가로 및 세로에 동일 선상에 있는 숫자들과 같아서는 안되고, 해당 빈 칸이 포함되어 있는 3 * 3 정사각형 내에 있는 숫자들과도 같아서는 안된다는 조건이 있습니다. 이와 관련된 로직은 다음과 같습니다.

 

    private static Set<Integer> getCandidates(int x, int y) {
        Set<Integer> candidates = new HashSet<>();
        Set<Integer> visited = new HashSet<>();
        for (int i = 1; i < 10; i++) {
            candidates.add(i);
        }

        for (int i = 0; i < 9; i++) {
            visited.add(board[x][i]);
            visited.add(board[i][y]);
        }

        int row = 3 * (((x + 3) / 3) - 1), col = 3 * (((y + 3) / 3) - 1);
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                visited.add(board[i][j]);
            }
        }

        candidates.removeAll(visited);

        return candidates;
    }

 

해당 빈 칸의 가로 및 세로에 동일 선상에 있는 숫자들과 해당 빈 칸이 포함되어 있는 3 * 3 정사각형 내에 있는 숫자들을 구해낸 뒤 이 숫자를 제외한 1 ~ 9의 수 목록을 얻어내도록 했습니다.

 

만일 이 조건에 해당되는 숫자가 없다면 그것은 앞서 빈 칸을 특정 수로 채웠던 방식으로는 스도쿠 조건을 충족시킬 수 없다는 것을 의미하게 됩니다. 따라서 이럴 경우에는 현재 메서드에서 빠져나와(return) 앞선 빈 칸에 설정했던 숫자를 다른 목록 상의 숫자로 바꾸어 다시 탐색하도록 했습니다.

 

최종적으로 모든 빈 칸을 채웠다는 것은 스도쿠의 조건을 충족시킨다는 것을 의미하게 됩니다. 따라서 해당 경우의 스도쿠 데이터를 출력시키고 프로그램을 종료시켰습니다. (문제에서는 빈 칸을 채우는 방법이 여러개가 있더라도 그 중 하나만 출력하는 것을 요구하고 있습니다.)

 

 

 

전체 소스 코드

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

class Main {

    static int[][] board;
    static int zeroCount = 0;

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

        board = new int[9][9];

        StringTokenizer st;

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

        fill(0, 0);
    }

    private static void fill(int start, int depth) {
        if (depth == zeroCount) {
            print();
            System.exit(0);
        }

        int x, y;
        for (int i = start; i < 81; i++) {
            x = i / 9;
            y = i % 9;

            if (board[x][y] == 0) {
                Set<Integer> candidates = getCandidates(x, y);
                if (candidates.size() == 0) {
                    return;
                }
                for (Integer candidate : candidates) {
                    board[x][y] = candidate;
                    fill(start + 1, depth + 1);
                    board[x][y] = 0;
                }
                return;
            }
        }
    }

    private static Set<Integer> getCandidates(int x, int y) {
        Set<Integer> candidates = new HashSet<>();
        Set<Integer> visited = new HashSet<>();
        for (int i = 1; i < 10; i++) {
            candidates.add(i);
        }

        for (int i = 0; i < 9; i++) {
            visited.add(board[x][i]);
            visited.add(board[i][y]);
        }

        int row = 3 * (((x + 3) / 3) - 1), col = 3 * (((y + 3) / 3) - 1);
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                visited.add(board[i][j]);
            }
        }

        candidates.removeAll(visited);

        return candidates;
    }

    private static void print() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.printf("%d ", board[i][j]);
            }
            System.out.println();
        }
    }
}

 

참고자료

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