[백준] 2580. 스도쿠 - Java

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

 

백트래킹 + 재귀를 활용한 문제

 

⭐️ 중요 포인트

1. blank의 가로, 세로, 해당 blank를 포함하는 정사각형 구역에서 주어진 num이 나오지 않았는지를 판별하는 메서드 구현

2. 재귀 내에서는 1~9(스도쿠에 들어갈 수 있는 수) 중 유효한 수만 선택하며 빈칸에 채워넣는 백트래킹 방식을 사용했다.

3. 만약 blankNum이 blanks.size()에 도달하지 못했다는 것은 중간에 잘못된 값을 선택해서 마지막 빈 칸 까지 채우지 못함을 의미한다.

4. blankNum == blanks.size()가 되면 모든 빈 칸이 유효한 값으로 채워졌고, 이후 최초로 나온 경우의 수에 대해서 board를 출력하면 된다. 이 때, System.exit(0);을 통해서 프로그램을 종료해도 되지만, 필자는 main 메서드에서 프로그램이 종료되는 형식을 선호하기 때문에 endFlag를 true로 변경하고 모든 호출된 재귀 메서드에 대해서 endFlag가 세워지면 탈출하는 조건을 넣어 첫 번째 경우의 수만 출력하도록 구현하였다.

 

필자는 해당 문제를 해결하며 시간초과 문제에 부딪혔다.

아래는 시간초과가 났던 코드와 개선하여 해결한 코드이다.

 

<각 blank별로 후보가 되는 수를 미리 찾고, 해당 수의 조합을 구하며 모든 칸이 채워질 때마다 성공했는지 판단하는 코드 - 시간초과>

1. blank별 후보를 찾는데 O((blanks.size() * 9) + (blanks.size() * 각 블랭크의 후보 숫자의 개수의 누적곱))...

딱 봐도 시간복잡도가 엄청 커보인다.. 그래서 후보들을 구하지 않고 바로바로 가능한 숫자를 고르며 빈 칸을 채워넣는 형식으로 변경하였다.

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

public class Main {

    static class Node {
        int x;
        int y;
        Set<Integer> candidates;

        Node(int x, int y) {
            this.x = x;
            this.y = y;
            this.candidates = new HashSet<>();

            for (int i = 1; i <= 9; i++) {
                candidates.add(i);
            }
        }
    }

    static BufferedReader br;
    static BufferedWriter bw;
    static int[][] board;
    static List<Node> blanks;
    static boolean endFlag;


    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        board = new int[9][9];
        blanks = new ArrayList<>();
        endFlag = false;

        for (int y = 0; y < 9; y++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int x = 0; x < 9; x++) {
                board[y][x] = Integer.parseInt(st.nextToken());

                if (board[y][x] == 0) {
                    blanks.add(new Node(x, y));
                }
            }
        }
    }

    static void solve() throws IOException {
        for (int i = 0; i < blanks.size(); i++) {
            checkCandidate(blanks.get(i));
//            System.out.println(blanks.get(i).x + " " + blanks.get(i).y + " " + blanks.get(i).candidates);
        }

        recursion(0);
    }

    static void recursion(int blankNum) throws IOException {
        if (endFlag) {
            return;
        }

        if (blankNum >= blanks.size()) {
            if (checkBlanks()) {
                printBoard();
                endFlag = true;

                bw.flush();
                bw.close();
                br.close();
                System.exit(0);
            }
            return;
        }

        Node blank = blanks.get(blankNum);

        for (Integer num: blank.candidates) {
            board[blank.y][blank.x] = num;
            recursion(blankNum + 1);
            board[blank.y][blank.x] = 0;
        }
    }

    static void printBoard() throws IOException {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                bw.write(board[y][x] + " ");
//                if (x < 8) {
//                    bw.write(" ");
//                }
            }
            bw.newLine();
//            if (y < 8) {
//                System.out.println();
//            }
        }
    }

    static void checkCandidate(Node node) throws IOException {
        for (int i = 0; i < 9; i++) {
            node.candidates.remove(board[node.y][i]);
            node.candidates.remove(board[i][node.x]);
        }
        int startX = (node.x / 3) * 3;
        int startY = (node.y / 3) * 3;

        for (int dy = 0 ; dy < 3; dy++) {
            for (int dx = 0; dx < 3; dx++) {
                node.candidates.remove(board[startY + dy][startX + dx]);
            }
        }
    }

    static boolean checkBlanks() throws IOException {
        for (int i = 0; i < blanks.size(); i++) {
            Node node = blanks.get(i);
            boolean[] isVisited = new boolean[10];
            for (int j = 0; j < 9; j++) {
                if (!isVisited[board[node.y][j]]) {
                    isVisited[board[node.y][j]] = true;
                } else {
                    return false;
                }
            }

            isVisited = new boolean[10];
            for (int j = 0; j < 9; j++) {
                if (!isVisited[board[j][node.x]]) {
                    isVisited[board[j][node.x]] = true;
                } else {
                    return false;
                }
            }

            int startX = (node.x / 3) * 3;
            int startY = (node.y / 3) * 3;

            isVisited = new boolean[10];
            for (int dy = 0 ; dy < 3; dy++) {
                for (int dx = 0; dx < 3; dx++) {
                    if (!isVisited[board[startY + dy][startX + dx]]) {
                        isVisited[board[startY + dy][startX + dx]] = true;
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        init();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

<정답 코드>

그때그때마다 빈칸에 유효한 숫자를 선택하여 채워넣고, 다음 빈칸으로 이동하는 재귀를 구현했다.

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

public class Main {

    static class Node {
        int x;
        int y;

        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static BufferedReader br;
    static BufferedWriter bw;
    static int[][] board;
    static List<Node> blanks;
    static boolean endFlag;


    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        board = new int[9][9];
        blanks = new ArrayList<>();
        endFlag = false;

        for (int y = 0; y < 9; y++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int x = 0; x < 9; x++) {
                board[y][x] = Integer.parseInt(st.nextToken());

                if (board[y][x] == 0) {
                    blanks.add(new Node(x, y));
                }
            }
        }
    }

    static void solve() throws IOException {
        recursion(0);
    }

    static void recursion(int blankNum) throws IOException {
        if (endFlag) {
            return;
        }
        
        // blankNum이 blanks.size()와 같아졌다는 것은 모든 blank에 유효한 값이 제대로 들어갔음을 의미
        // 여러 경우의 수 중 첫 번째 경우의 수에 걸려서 들어왔을 것임.
        if (blankNum == blanks.size()) {
            printBoard();
            
            // 최초로 나오는 경우의 수만 출력하면 되므로 endFlag를 활성화시켜 이후 경우의 수를 따지지 않고 recursion을 모두 종료하도록 하자
            // System.exit(0); 을 통해서 시스템을 종료할 수도 있지만 기존에 내가 사용하던 정해진 형식을 지키기 위해
            // endFlag를 활성화시키고, main 메서드에서 종료하도록 하기 위해 이렇게 구현했다.
            endFlag = true;
            return;
        }

        Node blank = blanks.get(blankNum);

        // 1~9까지 숫자중에 나오지 않은 수만 선택하며 빈 칸에 값을 채워넣어간다.
        // blankNum을 1씩 더해가며 마지막 blankNum을 채울 때까지 재귀를 반복한다.
        // 앞에 선택된 blank에 들어갈 num은 다음 blank에 채워질 num에 계속 누적하여 영향을 끼친다.
        for (int i = 1; i <= 9; i++) {
            if (checkValidNum(blank.x, blank.y, i)) {
                board[blank.y][blank.x] = i;
                recursion(blankNum + 1);
                board[blank.y][blank.x] = 0;
            }
        }
    }

    // 스도쿠 보드를 출력하는 메서드.
    static void printBoard() throws IOException {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                bw.write(board[y][x] + " ");
            }
            bw.newLine();
        }
    }

    // blank의 가로, 세로, 해당 blank를 포함하는 정사각형 구역에서 주어진 num이 나오지 않았는지를 판별하는 메서드
    static boolean checkValidNum(int x, int y, int num) throws IOException {
        for (int i = 0; i < 9; i++) {
            if (board[y][i] == num || board[i][x] == num) {
                return false;
            }
        }

        int startX = (x / 3) * 3;
        int startY = (y / 3) * 3;

        for (int dy = 0 ; dy < 3; dy++) {
            for (int dx = 0; dx < 3; dx++) {
                if (board[startY + dy][startX + dx] == num) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        init();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }
}