알고리즘 풀이 - 백준 2580(스도쿠, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

9줄에 걸쳐 스도쿠 상태값이 주어질 때, 스도쿠를 채워 넣는 경우를 출력하는 방법

 

 

2. 풀이

 

스도쿠를 풀 수 있는 경우의 수만 주어질 때, 스도쿠를 풀고 그 결과를 출력하는 문제로 현재 숫자가 들어있지 않은 모든 위치를 list에 저장한 뒤 각 위치에 넣을 수 있는 숫자를 조사하여 넣는 방식이다.

숫자가 지정되지 않은 list의 index를 재귀함수로 전달하고 모든 index 위치에 숫자가 들어갔다면 해당 결과를 출력하면 된다.

풀이 방식은 다음과 같다.

① 2차원 배열을 9x9 크기로 생성하여 주어진 값들을 모두 저장하되, 숫자가 0인 위치는 별도 list로 저장한다.
② 0부터 list의 index를 전달하여 재귀함수를 수행한다.
③ 1~9까지의 숫자 중 가능한 경우를 체크하고 넣을 수 있는 숫자를 넣은 뒤 다음 index로 넘어가 재귀를 수행한다.
④ list의 크기만큼의 index까지 전달되었다면 모든 미지정 숫자 위치에 숫자가 지정된 것이므로 true를 반환한다.
⑤ 재귀를 통해 true가 반환되었다면 가능한 경우이므로 추가 탐색 없이 true를 반환한다.
⑥ 반복문을 모두 수행했는데 true가 아닌 false가 반환되었다면 false를 반환하여 이전 재귀로 돌아간다.

 

여기서 ③의 부분에서 해당 숫자를 넣을 수 있는지는 아래의 3가지를 검토해야 한다.

1) 동일 Row에 같은 숫자가 있는지 점검하여 있으면 불가
2) 동일 Column에 같은 숫자가 있는지 점검하여 있으면 불가
3) 현재 위치의 3x3 정사각형에 같은 숫자가 있는지 점검하여 있으면 불가

여기서 3)을 구현하는데 시간이 좀 소요되었다. 3)을 점검하는 방법은 아래의 그림을 통해 쉽게 이해해보자.

각 위치는 위와 같이 index로 지정할 수 있는데, 만약 현재 비어 있는 숫자가 (4, 4)라고 가정해보자.

그러면, 체크해야 할 3x3 정사각형은 (3, 3) ~ (5, 5)까지이다. 여기서 Row / Column의 범위를 제한해주면 된다는 의미이다.

우선 Row 를 점검해보자. Row의 값이 3~5인 경우에는 3~5를 / 0~2인 경우에는 0~2를 / 6~8이면 6~8부분을 점검해야 한다.

어떻게 그 범위를 정할 수 있을까? 0~8까지 각 위치를 3으로 나누어보자. 그러면 아래와 같이 될 것이다.
(0, 0, 0 || 1, 1, 1, || 2, 2, 2)와 같이 나누어질 것이다. 그러면 여기에 3을 곱하면 다시 아래와 같이 된다.
(0, 0, 0 || 3, 3, 3, || 6, 6, 6)이 된다. 즉, 시작할 위치를 지정할 수 있게 된다.

다시 저 값에 2를 더한 위치까지만 모두 체크를 하면 된다. Column도 동일한 방식으로 체크를 할 수가 있게 된다.

 

따라서 (4, 4)를 점검하고자 한다면 (4 / 3 x 3) ~ (4 / 3 x 3) + 2까지, 즉, 3부터 5까지로 각 Row, Column을 제한 시킬 수 있게 된다. 이 내용을 코드를 통해 어떻게 구현할 수 있는지 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int[][] sudoku = new int[9][9];
    static ArrayList<Zero> list;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        // 숫자가 미지정된 위치를 저장하기 위한 List
        list = new ArrayList<>();
        for(int i=0; i < 9; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < 9; j++){
                sudoku[i][j] = Integer.parseInt(st.nextToken());
                if(sudoku[i][j] == 0){
                    list.add(new Zero(i, j));
                }
            }
        }
        
        // 0번째 위치부터 index 전달
        backTrack(0);
        StringBuilder sb = new StringBuilder();
        for(int i=0; i < 9; i++){
            for(int j=0; j < 9; j++){
                sb.append(sudoku[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
        
        br.close();
    }
    
    private static boolean backTrack(int idx){
        // 모든 list내 위치에 숫자가 지정되었다면 true 반환
        if(idx >= list.size()) return true;

        // 현재 index의 숫자가 정해지지 않은 다음 위치를 찾는다.
        Zero z = list.get(idx);
        for(int i=1; i <= 9; i++){
            // 현재 i라는 숫자를 입력 가능한지 체크한다.
            if(!check(z.y, z.x, i)) continue;
            
            // 가능한 경우 입력 수행
            sudoku[z.y][z.x] = i;
            
            // 다음 index 위치를 검사하여 true가 반환되었다면 추가 탐색 불필요하게 true 반환
            if(backTrack(idx+1)){
               return true; 
            }
        }
        
        // 위에서 true가 반환되지 않았다면 불가한 경우이므로 다시 0으로 지정한 뒤 false 반환
        sudoku[z.y][z.x] = 0;
        return false;
    }
    
    private static boolean check(int i, int j, int n){
        // 같은 행의 위치에 같은 숫자 있으면 불가
        for(int y=0; y < 9; y++){
            if(sudoku[y][j] == n) return false;
        }
        
        // 같은 열의 위치에 같은 숫자 있으면 불가
        for(int x=0; x < 9; x++){
            if(sudoku[i][x] == n) return false;
        }
        
        // 같은 3*3의 위치에 같은 숫자 있으면 불가
        int row = i / 3 * 3;
        int col = j / 3 * 3;
        for(int y=row; y < row+3; y++){
            for(int x=col; x < col+3; x++){
                if(sudoku[y][x] == n){
                    return false;
                }
            }
        }
        return true;
    }
}

// 숫자 미지정된 위치를 Object화 하는 class
class Zero{
    int y;
    int x;
    public Zero(int y, int x){
        this.y=y;
        this.x=x;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.