[백준 Java] 2580번 스도쿠

💡문제

[Gold IV] 스도쿠 - 2580

문제 링크

성능 요약

메모리: 16980 KB, 시간: 412 ms

---

🤔접근법

주어진 스도쿠에서 빈칸을 채워 완성된 스도쿠를 출력하는 문제

풀이법

⭕ 접근 방법. 백트래킹

1. 빈칸의 위치를 따로 저장한다.
2. 빈칸을 탐색하면서 1 부터 9까지 숫자를 시도 하며 규칙에 맞는지 확인
3. 빈 칸에 특정 숫자를 넣었을 경우 규칙에 위반하지 않는지 세가지 조건을 확인
4. 위 조건을 모두 만족한다면 다음 빈칸을 탐색
5. 모든 빈칸을 다 탐색한다면 출력하고 종료.

➡️ 해당 풀이법의 시간 복잡도 : $O(9^{빈칸의개수})$

---

😎SUCCESS

담박에 성공하지 못한 이유는 ?

• 빈칸에 숫자를 모두 채운 후에 스도쿠가 규칙을 만족하는지 확인하려고 했기 때문에 시간초과가 났다.
• 재귀에서 나온 후 보드를 원상복귀 시켜주지 않아 스도쿠 규칙을 확인할 때 만족하는 경우를 만족하지 않는다고 수행해버렸다.

---

👩‍💻 코드

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

public class Main {
    static int board[][]; // 스도쿠 보드
    static int num[]; // 각 숫자별 필요한 개수를 저장하는 배열
    
    // 빈 칸의 좌표를 저장하는 클래스
    static class EmptyPoint {
        int r; // 행
        int c; // 열

        public EmptyPoint(int r, int c) {
            this.r = r;
            this.c = c;
        }

        @Override
        public String toString() {
            return "emptyPoint{" +
                    "r=" + r +
                    ", c=" + c +
                    '}';
        }
    }
    
    static ArrayList<EmptyPoint> emptyPoints; // 빈 칸의 좌표를 저장하는 리스트
    static StringBuilder sb = new StringBuilder(); // 결과를 출력할 StringBuilder

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

        // 스도쿠 보드와 숫자 배열 초기화
        board = new int[9][9];
        num = new int[10]; // 숫자는 1부터 9까지 사용하므로 인덱스 0은 사용하지 않음
        
        // 빈 칸의 좌표를 저장하기 위한 리스트 초기화
        emptyPoints = new ArrayList<>();
        
        // 입력 받기
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                // 빈 칸인 경우 빈 칸 리스트에 좌표 추가
                if(board[i][j] == 0){
                    emptyPoints.add(new EmptyPoint(i,j));
                } else {
                    // 숫자가 채워진 경우 해당 숫자 카운트 증가
                    num[board[i][j]]++;
                }
            }
        }
        
        // 각 숫자별 필요한 개수 계산
        for (int i = 1; i < 10; i++) {
            num[i] = 9 - num[i];
        }

        // 백트래킹을 이용하여 빈 칸 채우기 시작
        getAnswer(0);
    }

    // 빈 칸 채우기
    private static void getAnswer(int depth) {
        // 모든 빈 칸을 채웠을 경우 결과를 출력하고 프로그램 종료
        if(depth == emptyPoints.size()){
            print();
            System.exit(0); // 프로그램 종료
            return;
        }

        // 현재 채워야 할 빈 칸의 좌표
        EmptyPoint p = emptyPoints.get(depth);

        // 현재 빈 칸에 1부터 9까지의 숫자를 시도하면서 규칙에 맞는지 확인
        for (int i = 1; i < 10; i++) {
            // 해당 숫자가 이미 필요한 개수만큼 사용되었다면 다음 숫자로 넘어감
            if(num[i] == 0) continue;
            // 현재 숫자가 규칙에 맞는 경우 해당 숫자 사용 표시하고 다음 빈 칸으로 이동
            if(check(p.r, p.c , i)){
                num[i]--; // 해당 숫자 사용 개수 감소
                board[p.r][p.c] = i; // 보드에 숫자 채우기
                getAnswer(depth+1); // 다음 빈 칸으로 이동
                // 백트래킹을 위해 다시 숫자 해제하고 이전 상태로 되돌아감
                num[i]++; // 해당 숫자 사용 개수 복구
                board[p.r][p.c] = 0; // 보드에서 숫자 지우기
            }
        }
    }

    // 스도쿠 규칙을 확인하는 함수
    private static boolean check(int r, int c, int value) {
        // 가로줄, 세로줄, 3x3 정사각형 안에 같은 숫자가 있는지 확인
        return checkRow(r, value) && checkCol(c, value) && check3by3(r, c, value);
    }

    // 3x3 정사각형 안에 같은 숫자가 있는지 확인하는 함수
    private static boolean check3by3(int r, int c, int value) {
        // 3x3 정사각형의 왼쪽 상단 좌표로 이동
        r = 3 * (r/3);
        c = 3 * (c/3);
        // 3x3 정사각형 내의 모든 칸을 확인하면서 중복된 숫자가 있는지 검사
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(board[r+i][c+j] == value) return false; // 중복된 숫자가 있으면 false 반환
            }
        }
        return true; // 중복된 숫자가 없으면 true 반환
    }

    // 세로줄에 같은 숫자가 있는지 확인하는 함수
    private static boolean checkCol(int c, int value) {
        // 세로줄의 모든 칸을 확인하면서 중복된 숫자가 있는지 검사
        for (int j = 0; j < 9; j++) {
            if(board[j][c] == value) return false; // 중복된 숫자가 있으면 false 반환
        }
        return true; // 중복된 숫자가 없으면 true 반환
    }

    // 가로줄에 같은 숫자가 있는지 확인하는 함수
    private static boolean checkRow(int r, int value) {
        // 가로줄의 모든 칸을 확인하면서 중복된 숫자가 있는지 검사
        for (int j = 0; j < 9; j++) {
            if(board[r][j] == value) return false; // 중복된 숫자가 있으면 false 반환
        }
        return true; // 중복된 숫자가 없으면 true 반환
    }

    // 결과를 출력하는 함수
    private static void print() {
        // 스도쿠 보드 출력
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(board[i][j] +" "); // 숫자와 공백을 StringBuilder에 추가
            }
            sb.append("\n"); // 가로 줄이 끝나면 개행 문자 추가
        }
        System.out.println(sb.toString()); // 결과 출력
    }
}