[백준2580] 스도쿠 / Java

문제주소 :www.acmicpc.net/problem/2580

 

---

<문제 설명>

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

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

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

제한

• baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
  • C++14: 80ms
  • Java: 292ms
  • PyPy3: 1172ms

 

<풀이법>

▒ 한줄 개념: 백트래킹 알고리즘 ▒ 

기본적인 백트래킹 알고리즘 문제 중 하나입니다.

백트래킹 알고리즘이란 DFS로 탐색을 진행하면서, 혹시 정답이 나올 수 없다면(유망하지 않다면) 뒤로 돌아 올라가는 알고리즘입니다.

 

 https://commons.wikimedia.org/wiki/File:Sudoku_solved_by_bactracking.gif

 

이번 문제에서 알고리즘의 개요는 다음과 같습니다.

 

1.입력에 따른 현재 스도쿠 판 완성:

판을 만들면서 동시에 빈칸의 위치를 ArrayList로 저장 (이 빈칸의 위치를 저장하여 사용함으로서 스도쿠 판을 전체 탐색하는 시간적 비용을 줄입니다.)

for(int i=0; i<9; i++){ // 입력에 따라 현재 스도쿠 판 만들기
	for(int j=0; j<9; j++){
		matrix[i][j] = sc.nextInt();
		if(matrix[i][j] == 0) empty_spots.add(new int[]{i,j});
	}
}

 

2. DFS 실행 :

빈칸 위치를 담은 ArrayList의 사이즈와 DFS의 깊이(count)가 동일할 때 종료, 그 외에는 1~9까질를 차례대로 유망성을 판단하여 삽입하고 스도쿠 판을 채워갑니다.

static boolean sudoku(int count){
	if(count == empty_spots.size()){ // 종료조건
    	return true;
    }
    else{
        int[] position = empty_spots.get(count); // 다음 빈칸의 위치 가져옴
        int n = position[0]; 
        int m = position[1];
        for(int i = 1; i<10; i++){ // 1~9까지 반복문,
            if(isPromising(matrix, n, m, i)){ // 유망성 판단
                matrix[n][m] = i; 
                if (sudoku(count+1)) return true; // 끝에 도달했으면 return true
                else matrix[n][m] = 0; // 끝에 도달하지 못했으면 해당 칸 초기화
            }
        }
    }
    return false;
}

 

3. 유망성 판단:

이 문제에서 유망성 판단에는 2가지 경우가 있습니다. 

• 가로, 세로에 동일한 숫자가 있으면 안된다.
• 해당 블럭(3x3)내에 동일한 숫자가 있으면 안된다.

유망성 판단의 두 가지 조건

따라서 유망성을 판단할 때 이 두 가지 조건을 확인해주어야 합니다.

블록 내 판단을 할 때에는 n과 m을 각각 3으로 나눠 블록의 인덱스를 알아오고, 해당 블록 인덱스에 0~3을 더해가며 탐색을 진행하게 됩니다.

static boolean isPromising(int[][] matrix, int n, int m, int num){
    int len = matrix.length;
    int n_block = n / 3; // 현재 블록의 세로 위치
    int m_block = m / 3; // 현재 블록의 가로 위치

    for(int i =0; i<len; i++){ // 조건1: 가로세로 판단
        if(matrix[n][i] == num) return false;
        if(matrix[i][m] == num) return false;
    }

    for(int i=0; i<3; i++){ // 조건2: 같은 블록 내 판단
        for(int j=0; j<3; j++){
            if(matrix[(n_block*3)+i][(m_block*3)+j] == num)
                return false;
        }
    }

    return true;
}

 

<코드(Java)>

package Baekjoon;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Sudoku_2580 {

    static ArrayList<int[]> empty_spots = new ArrayList();
    static int[][] matrix = new int[9][9];

    public static void main(String[] args){
        BufferedWriter buf = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);

        for(int i=0; i<9; i++){ // 입력에 따라 현재 스도쿠 판 만들기
            for(int j=0; j<9; j++){
                matrix[i][j] = sc.nextInt();
                if(matrix[i][j] == 0) empty_spots.add(new int[]{i,j});
            }
        }

        sudoku(0); // 스도쿠 실행

        try { // BufferedWriter를 이용하여 출력
            for(int i=0; i<9; i++) {
                for (int j = 0; j < 9; j++) {
                    buf.write(String.valueOf(matrix[i][j]));
                    buf.write(" ");
                }
                buf.newLine();
            }
            buf.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static boolean sudoku(int count){
        if(count == empty_spots.size()){ // 종료조건
            return true;
        }
        else{
            int[] position = empty_spots.get(count); // 다음 빈칸의 위치 가져옴
            int n = position[0];
            int m = position[1];
            for(int i = 1; i<10; i++){ // 1~9까지 반복문,
                if(isPromising(matrix, n, m, i)){ // 유망성 판단
                    matrix[n][m] = i;
                    if (sudoku(count+1)) return true; // 끝에 도달했으면 return true
                    else matrix[n][m] = 0; // 끝에 도달하지 못했으면 해당 칸 초기화
                }
            }
        }
        return false;
    }


    static boolean isPromising(int[][] matrix, int n, int m, int num){
        int len = matrix.length;
        int n_block = n / 3; // 현재 블록의 세로 위치
        int m_block = m / 3; // 현재 블록의 가로 위치

        for(int i =0; i<len; i++){ // 조건1: 가로세로 판단
            if(matrix[n][i] == num) return false;
            if(matrix[i][m] == num) return false;
        }

        for(int i=0; i<3; i++){ // 조건2: 같은 블록 내 판단
            for(int j=0; j<3; j++){
                if(matrix[(n_block*3)+i][(m_block*3)+j] == num)
                    return false;
            }
        }

        return true;
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest