[BAEKJOON] 2580 스도쿠

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Gold4
• 문제내용:
  • 9 × 9 행렬 스도쿠 문제가 주어진다.
  • 0이 빈값이다.
  • 정답을 채워라
• 사이트 주소: https://www.acmicpc.net/problem/2580

2580번: 스도쿠

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

 

 이번 문제보면 위의 그림 처럼 스도쿠 문제 정답을 내는 것이다.

 스도쿠의 규칙은 다음과 같다.

• 1 ~ 9까지 조건에 맞게 채워야 한다.
• 1 ~ 9 가로 세로 중복이 없어야 한다.
• 1 ~ 9 3 × 3 박스안에 다 채워야 하는데 중복이 없어야 한다.

위 3개 조건 만 알면 된다. 하지만 일반적으로 탐색해서 찾기에는  앞에 숫자가 들어갈 값이 없으면 뒤에 넣었던 숫자를 다시 탐색을 해야 되는 경우가 있어서 백트레킹 방법으로 문제를 풀어야 한다.

1.  9 × 9 배열을 선언한 다음 입력값에 맞게 데이터를 집어 넣는다.
2. 인덱스 0, 0 부터 탐색을 한다. 
3. 만약 기존 값이 들어가 있으면 다음 비어 있는 값을 찾는다.
4. 0인 경우 1 ~ 9 한개씩 값이 위에 조건에 맞는지 확인한다.
5. 값이 맞는 경우 값을 넣고 함수 재호출하면서 다음 비어 있는 값을 찾는다. 만약 다시 돌아올 경우 다시 비어 있는 값으로 설정한다.
6. 다 찾았을 경우 정답을 출력한다.  

 

Code

Python

# 전체 값이 채워져있는지 확인
def is_full(arrays, p):
    for i in range(9):
        for j in range(9):
            if(arrays[i][j] == 0): # 비어 있는 값이 있는 경우 위치 반환
                p[0], p[1] = i, j
                return False
    return True

# 유효 값 확인
def check_value(arrays, row, col, num):
    return check_closs(arrays, row, col, num) and check_box(arrays, row - row % 3, col - col % 3, num)

# 가로, 세로 확인
def check_closs(arrays, row, col, num):
    for i in range(9):
        if(arrays[row][i] == num or arrays[i][col] == num): return False
    return True

# 박스 영역 확인
def check_box(arrays, row, col, num):
    for i in range(3):
        for j in range(3):
            if arrays[row + i][col +j] == num: return False
    return True


def sudoku(arrays):
    p = [0, 0]
    if is_full(arrays, p): return True
    row, col = p[0], p[1]
    for num in range(1, 10):
        if(check_value(arrays, row, col, num)):
            arrays[row][col] = num
            if(sudoku(arrays)): return True;
            arrays[row][col] = 0
    return False
            

matrix = []
for _ in range(9):
    matrix.append(list(map(int, input().split())))

sudoku(matrix)
for i in range(9):
    for j in range(9):
        print(matrix[i][j], end = ' ')
    print()

Java

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

public class Main {

	static int[][] matrix = new int[9][9];
	
	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++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		sudoku(0, 0);

	}
		
	/**
	 *  sudoku
	 */
	public static void sudoku(int row, int col) {
		
		// 한 행이 끈나면 다음행으로 이동
		if(col == 9) {
			sudoku(row + 1, 0);
			return;
		}
		// 9개 행을 탐색을 끝나면 결과를 출력하고 종료한다.
		if(row == 9) {
			StringBuilder sb = new StringBuilder();
			for(int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(matrix[i][j]).append(' ');
				}
				sb.append("\n");
			}
			
			System.out.println(sb);
			System.exit(0);
		}
		if(matrix[row][col] == 0) {
			
			for(int num = 1; num <= 9; num++) {
				if(is_value(matrix, row, col, num)) {					
					matrix[row][col] = num;
					sudoku(row, col + 1);
					
				}
			}
			matrix[row][col] = 0;
			return;
		}
		sudoku(row, col + 1);
		
	}
	

	// 스도쿠의 조건이 만족하는지 확인
	public static boolean is_value(int[][] array, int row, int col, int num) {
		return is_closs(array, row, col, num) && is_box(array, row - row % 3 ,col - col %3, num);
	}
	
	// 가로, 세로중에 중복되는 숫자 확인
	public static boolean is_closs(int[][] array, int row, int col, int num) {
		for(int i = 0; i < 9; i++) {
			if (array[row][i] == num || array[i][col] == num) return false;
		}	
		return true;
	}
	
	// 본인이 속한 영역이 중복 되는지 확인
	public static boolean is_box(int[][] array, int row, int col, int num) {
		for(int j = 0; j < 3; j++) {
			for (int i = 0; i < 3; i ++) {
				if (array[row + j][col + i] == num) return false;
			}
		}
		return true;
	}
		
}