99클럽 코테 스터디 35일차 TIL + 스도쿠 (백트레킹)

 

 

 

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 백준 - 스도쿠 (문제 링크)
• 백트래킹

 

 

---

 

 

문제 설명

스도쿠는 9x9 격자판에서 1부터 9까지의 숫자를 채워넣는 퍼즐 게임입니다. 이 게임의 규칙은 다음과 같습니다:

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 합니다.
2. 굵은 선으로 구분된 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 합니다.

초기 스도쿠 판에 쓰여진 숫자들이 주어질 때, 빈 칸을 규칙에 맞게 채워서 스도쿠를 완성하는 프로그램을 작성하세요. 여러 개의 해답이 있을 수 있지만, 그 중 하나만 출력하면 됩니다.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 초기 스도쿠판의 각 줄에 쓰여 있는 숫자가 주어집니다. 빈 칸의 경우 0이 주어집니다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 출력합니다.

입출력 예

예제 입력 1

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

예제 출력 1

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

 

 

---

 

 

문제 접근

1. 문제 이해
   • 스도쿠 퍼즐은 빈 칸(0)을 규칙에 맞게 채우는 것입니다.
   • 가로, 세로, 3x3 박스의 규칙에 맞게 1부터 9까지의 숫자를 채워넣어야 합니다.
   • 백트래킹을 통해 가능한 모든 숫자를 시도해보고, 규칙에 맞는 경우 다음 칸으로 진행합니다.
2. 풀이 방법
   • 백트래킹(Backtracking)을 이용해 빈 칸을 채워나갑니다.
   • 각 칸에 1부터 9까지의 숫자를 시도하며, 가로, 세로, 3x3 박스 규칙을 만족하는지 확인합니다.
   • 규칙을 만족하는 경우 해당 숫자를 채우고 다음 칸으로 이동합니다.
   • 만약 모든 칸이 채워지면 스도쿠를 출력하고 프로그램을 종료합니다.

 

 

풀이 - Java 코드

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

public class Main {

    private static int[][] board = new int[9][9];
    private static int boardLength = 9;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        sudoku(0, 0);

        br.close();

    }

    private static void sudoku(int row, int col) {

        if (col == boardLength) {
            sudoku(row + 1, 0);
            return;
        }

        // 행과 열이 모두 채워졌을 경우 출력 후 종료
        if (row == boardLength) {
            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 이라면 1부터 9까지 중 가능한 수 탐색
        if (board[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {
                // i 값이 중복되지 않는지 검사
                if (possibility(row, col, i)) {
                    board[row][col] = i;
                    sudoku(row, col + 1);
                }
            }
            board[row][col] = 0; // 해결하지 못하면 다시 돌아와서 0 으로 세팅후 해결못한 백트레킹
            return;
        }

        sudoku(row, col + 1);

    }

    private static boolean possibility(int row, int col, int value) {

        // 가로 검사
        for (int i = 0; i < boardLength; i++) {
            if(board[row][i] == value){
                return false;
            }
        }

        // 세로 검사
        for (int i = 0; i < boardLength; i++) {
            if(board[i][col] == value){
                return false;
            }
        }

        // 3*3 칸 검사
        int row3 = (row / 3) * 3;
        int col3 = (col / 3) * 3;

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

        return true;
    }
}

풀이 설명

1. 초기화
   • 9x9 크기의 스도쿠 보드를 입력받아 초기화합니다. 이후 백트래킹을 통해 빈 칸을 채우기 시작합니다.
2. 백트래킹을 이용한 빈 칸 채우기
   • sudoku(int row, int col) 메서드는 현재 위치 (row, col)에 대해 가능한 숫자를 탐색하여 보드를 채웁니다.
   • 보드의 끝에 도달하면 채워진 결과를 출력하고 프로그램을 종료합니다.
   • 빈 칸에 대해서는 1부터 9까지의 숫자를 시도하며, 규칙에 맞는 숫자가 발견되면 그 숫자를 채우고 다음 칸으로 넘어갑니다.
3. 가능한 숫자 검토
   • possibility(int row, int col, int value) 메서드를 통해 특정 위치에 숫자를 채울 수 있는지 확인합니다.
   • 가로, 세로, 3x3 박스를 모두 검사하여 해당 숫자가 중복되지 않으면 true를 반환하고, 중복되면 false를 반환합니다.
4. 결과 출력 및 종료
   • 모든 칸이 채워지면 스도쿠 보드를 출력하고 프로그램을 종료합니다.

 

 

---

 

 

마무리하며

이번 문제는 백트래킹을 사용해 스도쿠 퍼즐을 완성하는 과정에서 가능한 모든 경우를 탐색하며 해를 찾는 방법으로 문제를 해결하였습니다.