[백준/Java] 2580: 스도쿠

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

백트래킹은 해도해도 어렵다

아래 잘 정리돼있는 블로그 글 보면서도 한참 헷갈렸음

🚀 참고
https://st-lab.tistory.com/119

풀이1 (참고한 블로그와 동일)

입력받은 값을 2차원 int 배열에 저장
sudoku() 재귀함수 작성
1. for문을 이용하여 스도쿠 차례대로 탐색
2. 빈 칸을 만날 때마다 숫자(1~9) 대입 시도
  1. 해당 빈 칸이 위치하는 행, 열, 3X3 박스를 확인 (calculate 함수 호출)
    - calculate() 작성
      - 빈 칸의 위치와 확인하려는 숫자값 매개변수로 받음 (row, col, value)
      - 행, 열, 박스 각각 확인하여 이중 중복되는 숫자가 있으면 바로 false 리턴
        
        박스를 확인할 땐 해당 빈칸이 포함되는 박스가 시작되는 위치를 확인하여 진행
      - 모두 통과하면 true 리턴
  2. 입력하려는 숫자가 행/열/박스 내에 이미 존재하면 그 다음 숫자로 확인
3. 1~9 중 알맞은 값을 발견한 경우 빈 칸 위치에 값 저장 후 스도쿠 다음 칸으로 이동(재귀)
4. 이후 알맞은 값을 발견하지 못한 경우엔 백트래킹을 통해 돌아와 다시 0으로 저장

코드

main

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

   board = new int[9][9];

   // 입력 받은 값을 2차원 int 배열에 저장
    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());
        }
    }
    
    // 첫 번째 칸부터 확인
    sudoku(0, 0);
}

sudoku

빈 칸을 탐지할 때마다 숫자(1~9) 대입 시도
알맞은 숫자를 확인하면 해당 값을 빈 칸에 저장 후 다음 칸으로 이동(재귀함수 실행)
알맞은 숫자를 찾아내지 못하면 백트래킹 하여 저장된 값을 다시 0으로 변경

static void sudoku(int row, int col) {
    // 열의 값이 스도쿠 범위를 넘은 경우
    if (col >= 9) {
        // 다음 행으로 이동
        sudoku(row + 1, 0);
        return;
    }

    // 행의 값이 스도쿠 범위를 넘은 경우
    // 즉 스도쿠가 전부 채워진 경우
    if (row >= 9) {
        // 스도쿠 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(board[i][j]).append(' ');
            }
            sb.append('\n');
        }

        System.out.println(sb);
        System.exit(0); // 시스템 종료
    }

    // 빈 칸(0)인 경우 숫자 대입 시도
    if (board[row][col] == 0) {
        for (int i = 1; i <= 9; i++) {
            if (calculate(row, col, i)) {   // 알맞은 값인지 확인
                board[row][col] = i;    // 숫자 넣기
                sudoku(row, col + 1);   // 다음 칸으로 이동
            }
        }

        // 빈 칸임에도 숫자가 채워지지 않은 경우
        board[row][col] = 0;    // 백트래킹(원상복구)
        return;
    }

    // 빈 칸이 아닌 경우 다음 칸으로 이동
    sudoku(row, col + 1);
}

calculate

빈 칸의 위치와 확인하려는 숫자를 매개변수로 전달 받음
빈 칸과 같은 행, 열, 3X3 박스 내에 확인하려는 숫자가 이미 존재하는지 확인
존재하는 경우 false 리턴
모든 조건을 통과한 경우(중복 숫자가 없는 경우) true 리턴

static boolean calculate(int row, int col, int value) {
    // 같은 행에 value가 존재하는지 확인
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == value) {
            return false;
        }
    }

    // 같은 열에 value가 존재하는지 확인
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == value) {
            return false;
        }
    }

    // 3x3 박스 내에 value가 존재하는지 확인
    // 박스 시작 위치
    int startX = (row / 3) * 3;
    int startY = (col / 3) * 3;

    for (int i = startX; i < startX+3; i++) {
        for (int j = startY; j < startY+3; j++) {
            if (board[i][j] == value) {
                return false;
            }
        }
    }

    return true;
}

전체

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

public class Main {

    static int[][] board;   // 스도쿠판

    /**
     * 특정 숫자가 입력될 수 있는지 확인
     * 입력될 수 없는 경우(이미 해당 숫자가 열or행or박스 내에 존재하는 경우) false 리턴
     *
     * @param row 행
     * @param col 열
     * @param value 입력하려는 숫자
     * @return
     */
    static boolean calculate(int row, int col, int value) {
        // 같은 행에 value가 존재하는지 확인
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == value) {
                return false;
            }
        }

        // 같은 열에 value가 존재하는지 확인
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == value) {
                return false;
            }
        }

        // 3x3 박스 내에 value가 존재하는지 확인
        // 박스 시작 위치
        int startX = (row / 3) * 3;
        int startY = (col / 3) * 3;

        for (int i = startX; i < startX+3; i++) {
            for (int j = startY; j < startY+3; j++) {
                if (board[i][j] == value) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * 빈칸을 탐지할 때마다 숫자 대입 시도
     * 알맞은 숫자를 확인하면 해당 값을 배열에 저장한 후 재귀함수 실행
     * 알맞은 숫자를 확인하지 못하면 백트래킹
     */
    static void sudoku(int row, int col) {
        // 열의 값이 스도쿠 범위를 넘은 경우
        if (col >= 9) {
            // 다음 행으로 이동
            sudoku(row + 1, 0);
            return;
        }

        // 행의 값이 스도쿠 범위를 넘은 경우
        // 즉 스도쿠가 전부 채워진 경우
        if (row >= 9) {
            // 스도쿠 출력
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(board[i][j]).append(' ');
                }
                sb.append('\n');
            }

            System.out.println(sb);
            System.exit(0); // 시스템 종료
        }

        // 빈 칸(0)인 경우 숫자 대입 시도
        if (board[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (calculate(row, col, i)) {   // 알맞은 값인지 확인
                    board[row][col] = i;    // 숫자 넣기
                    sudoku(row, col + 1);   // 다음 칸으로 이동
                }
            }

            // 빈 칸임에도 숫자가 채워지지 않은 경우
            board[row][col] = 0;    // 백트래킹(원상복구)
            return;
        }

        // 빈 칸이 아닌 경우 다음 칸으로 이동
        sudoku(row, col + 1);
    }

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

       board = new int[9][9];

       // 입력 받은 값을 2차원 int 배열에 저장
        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());
            }
        }
        
        sudoku(0, 0);
    }
}

챗지피티한테 상단 코드를 더 효율적으로 쓸 수 있냐고 물어봄

풀이2

calculate 함수 최적화
- 현재 calculate 함수는 행, 열, 박스를 각각 탐색하며 중복 검사
- 이를 각각 boolean 배열을 생성하여 검사하면 더 빠르게 확인 가능 O(1)
  - rowCheck[row][num]: 해당 row에 num이 존재하는지 체크
  - colCheck[col][num]: 해당 col에 num이 존재하는지 체크
  - boxCheck[boxIndex][num]: 해당 3×3 박스에 num이 존재하는지 체크
sudoku의 재귀 탐색 최적화
- 현재는 (row, col)을 좌에서 우로, 행 단위로 이동하는 방식
- list에 0인 칸만 먼저 모아두고 우선적으로 채우는 방식으로 변경하면 불필요한 연산을 줄일 수 있음
  - List<int[]> emptySells: 빈 칸의 위치를 저장

코드

getBoxIndex

빈 칸의 row, col 값을 받아옴
해당 빈 칸이 스도쿠의 몇 번째 박스에 위치하는지 확인

static int getBoxIndex(int row, int col) {
    return (row / 3) * 3 + (col / 3);
}

sudoku

emptySells를 통해 각 빈 칸을 한 개씩 확인
rowCheck, colCheck, boxCheck을 이용해 숫자(1~9)가 행, 열, 박스에 이미 존재하는지 확인
- 존재하지 않는 경우(각 boolean 배열의 [num]값이 전부 false인 경우)
  - 스도쿠의 빈 칸에 해당 숫자를 저장하고 각 boolean 배열의 [num]값을 true로 저장
  - 다음 칸 탐색 (재귀)
- 존재하는 경우
  - false 값 리턴, 이후 백트래킹 되며 다시 0이 저장됨

static boolean sudoku(int index) {
    // 빈 칸을 전부 확인한 경우 (스도쿠가 문제 없이 채워진 경우)
    if (index == emptyCells.size()) {
        // 스도쿠 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(board[i][j]).append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb);

        // 프로그램 종료
        System.exit(0);
    }

    // 빈 칸 위치 확인
    int[] pos = emptyCells.get(index);
    int row = pos[0], col = pos[1];

    // 해당 빈칸이 스도쿠의 몇 번째 박스에 위치하는지 확인
    int boxIndex = getBoxIndex(row, col);

    for (int i = 1; i <= 9; i++) {
        // 숫자가 행, 열, 박스 모두에 존재하지 않는 경우
        if (!rowCheck[row][i] && !colCheck[col][i] && !boxCheck[boxIndex][i]) {
            board[row][col] = i;    // 빈 칸에 숫자 입력
            rowCheck[row][i] = colCheck[col][i] = boxCheck[boxIndex][i] = true;

            // 다음 칸 탐색
            if (sudoku(index + 1)) {    // 스도쿠가 문제 없이 채워짐
                return true;
            }

            // 스도쿠가 제대로 채워지지 못하고 백트래킹 됨
            board[row][col] = 0;
            rowCheck[row][i] = colCheck[col][i] = boxCheck[boxIndex][i] = false;
        }
    }

    // 숫자가 행, 열, 박스에 이미 존재하는 경우
    return false;
}

main

숫자를 입력 받아 2차원 int 배열에 저장
빈 칸(0)일 경우 emptyCells에 해당 빈 칸의 위치 저장
빈 칸이 아닌 경우 각 행, 열, 박스 boolean 배열에 true 저장

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    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) { // 빈 칸인 경우
                emptyCells.add(new int[]{i, j});
            } else {    // 빈 칸이 아닌 경우
                int num = board[i][j];

                // 현재 행, 열, 박스에 숫자가 존재한다고 표시
                rowCheck[i][num] = true;
                colCheck[j][num] = true;
                boxCheck[getBoxIndex(i, j)][num] = true;
            }
        }
    }

    sudoku(0);
}

전체

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

public class Main {

    static int[][] board = new int[9][9];
    static boolean[][] rowCheck = new boolean[9][10];   // 행 확인
    static boolean[][] colCheck = new boolean[9][10];   // 열 확인
    static boolean[][] boxCheck = new boolean[9][10];   // 박스 확인
    static List<int[]> emptyCells = new ArrayList<>();  // 빈 칸 위치

    static int getBoxIndex(int row, int col) {
        return (row / 3) * 3 + (col / 3);
    }

    static boolean sudoku(int index) {
        // 빈 칸을 전부 확인한 경우 (스도쿠가 문제 없이 채워진 경우)
        if (index == emptyCells.size()) {
            // 스도쿠 출력
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(board[i][j]).append(' ');
                }
                sb.append('\n');
            }
            System.out.print(sb);

            // 프로그램 종료
            System.exit(0);
        }

        // 빈 칸 위치 확인
        int[] pos = emptyCells.get(index);
        int row = pos[0], col = pos[1];

        // 해당 빈칸이 스도쿠의 몇 번째 박스에 위치하는지 확인
        int boxIndex = getBoxIndex(row, col);

        for (int i = 1; i <= 9; i++) {
            // 숫자가 행, 열, 박스 모두에 존재하지 않는 경우
            if (!rowCheck[row][i] && !colCheck[col][i] && !boxCheck[boxIndex][i]) {
                board[row][col] = i;    // 빈 칸에 숫자 입력
                rowCheck[row][i] = colCheck[col][i] = boxCheck[boxIndex][i] = true;

                // 다음 칸 탐색
                if (sudoku(index + 1)) {    // 스도쿠가 문제 없이 채워짐
                    return true;
                }

                // 스도쿠가 제대로 채워지지 못하고 백트래킹 됨
                board[row][col] = 0;
                rowCheck[row][i] = colCheck[col][i] = boxCheck[boxIndex][i] = false;
            }
        }

        // 숫자가 행, 열, 박스에 이미 존재하는 경우
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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) { // 빈 칸인 경우
                    emptyCells.add(new int[]{i, j});
                } else {    // 빈 칸이 아닌 경우
                    int num = board[i][j];

                    // 현재 행, 열, 박스에 숫자가 존재한다고 표시
                    rowCheck[i][num] = true;
                    colCheck[j][num] = true;
                    boxCheck[getBoxIndex(i, j)][num] = true;
                }
            }
        }

        sudoku(0);
    }
}

저작자표시 (새창열림)

'코딩테스트 > 백준' 카테고리의 다른 글

[백준/Java] 1904: 01타일 (0)	2025.04.30
[백준/Java] 9184: 신나는 함수 실행 (0)	2025.03.09
[백준 2428/자바] 표절 (0)	2024.12.07
[백준 9935/자바] 문자열 폭발 (1)	2024.07.03
[백준 2606/자바] 바이러스 (0)	2024.07.03

종합장

[백준/Java] 2580: 스도쿠

풀이1 (참고한 블로그와 동일)

코드

풀이2

코드

'코딩테스트 > 백준' 카테고리의 다른 글

댓글

티스토리툴바

[백준/Java] 2580: 스도쿠

풀이1 (참고한 블로그와 동일)

코드

풀이2

코드

'코딩테스트 > 백준' 카테고리의 다른 글

관련글

댓글

티스토리툴바