[BAEKJOON] 2239 스도쿠

문제 요약

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

2239번: 스도쿠

문제풀이

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

https://jih3508.tistory.com/84

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

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

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

위 조건은 아래 코드처럼 구현 하면 된다.

1 ~ 9 가로 세로 중복이 없어야 한다.

 Python

def checkedCross(row, col, num, arrays):
    for k in range(size):
        if(arrays[row][k] == num or arrays[k][col] == num):
            return False
    return True

Java

public static boolean checkedCross(int row, int col, int num, int[][] arrays){
		
    for(int k = 0; k < size; k++) {
        if(arrays[k][col] == num || arrays[row][k] == num) {
            return false;
        }
    }
    return true;
}

 

 

1 ~ 9 3 × 3 박스안에 다 채워야 하는데 중복이 없어야 한다.

 박스의 영역은 확인하기 위해서  row - row % 3, col - col % 3으로 박스 가로 세로 위치를 처음 위치로 지정하고 3 × 3 중복값이 있는지 찾아 낸다.

Python

checkedBox(row - row % 3, col - col % 3, num, arrays)

def checkedBox(row, col, num, arrays):
    for i in range(3):
        for j in range(3):
            if(arrays[row + i][col + j] == num):
                return False
    return True

Java

checkedBox(row - row % 3, col - col % 3, num, arrays);

public static boolean checkedBox(int row, int col, int num, int[][] arrays) {
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            if(arrays[row + i][col + j] == num) {
                return false;
            }
        }
    }
    return true;
}

 

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

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

 

Code

Python

 파이썬은 PyPy로 해야 통과가 된다.

size = 9 # 스도쿠 가로, 세로 크기

# 스도쿠 결과 출력
def printSudoku(arrays):
    for array in arrays:
        print(''.join(map(str, array)))

# 스도쿠 비어 있는지 찾기
def isBlank(arrays):
    global x, y
    for i in range(size):
        for j in range(size):
            # 빈값이면 빈 값 위치지정 하고 반환 한다.
            if(arrays[i][j] == 0):
                x, y = i, j
                return False
    return True

# 가로, 세로 중복값 있는지 확인
def checkedCross(row, col, num, arrays):
    for k in range(size):
        if(arrays[row][k] == num or arrays[k][col] == num):
            return False
    return True

# 박스 영역안 중복값 있는지 확인
def checkedBox(row, col, num, arrays):
    for i in range(3):
        for j in range(3):
            if(arrays[row + i][col + j] == num):
                return False
    return True

# 스도쿠 조건 맞으면 참으로 반환 한다.
def checked(row, col, num, arrays):
    return checkedCross(row, col, num, arrays) and checkedBox(row - row % 3, col - col % 3, num, arrays)


def sudoku(arrays):
    global x, y
    # 빈값있는지 확인하고 없으면 스도쿠 출력하고 종료한다.
    if(isBlank(arrays)):
        printSudoku(arrays)
        exit()
    else:
        row, col = x, y
        for num in range(1, size+1):
            # 1부터 9까지 대입해보고 중복값이 없으면 값을 집어 넣고 다음 진행한다.
            if(checked(row, col, num, arrays)):
                arrays[row][col] = num
                sudoku(arrays)
                arrays[row][col] = 0


arrays = [list(map(int, list(input()))) for _ in range(size)]
sudoku(arrays)

Java

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

public class Main {
	
	static final int size = 9; // 스고쿠 가로, 세로 크기
	static int x, y;
	

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] strings;
		
		int[][] arrays = new int[size][size];
		Arrays.stream(arrays).forEach(array -> {
			Arrays.setAll(array, num -> 0);
		});
		for(int i = 0; i < size; i++) {
			strings = br.readLine().split("|");
			for(int j = 0; j< size; j++) {
				arrays[i][j] = Integer.parseInt(strings[j]);
			}
		}
		sudoku(arrays);
	}
	
	
	public static void sudoku(int[][] arrays) {
		
		// 빈값이 없으면 스도쿠 출력하고 종료한다.
		if(isBlank(arrays)) {		
			printSudoku(arrays);
			System.exit(0);
		}else {
			int row = x;
			int col = y;
			for(int num = 1; num <= size; num++) {
				if(checked(row, col, num, arrays)) {
					arrays[row][col] = num;
					sudoku(arrays);
					arrays[row][col] = 0;
				}
			}
		}
	}
	
	public static boolean checked(int row, int col, int num, int[][] arrays) {
		
		return checkedCross(row, col, num, arrays) && 
				checkedBox(row - row % 3, col - col % 3, num, arrays); // row % 3, col % 3 박스안에 
	}
	
	/*
	 * 가로세로 중복 값 찾기
	 */
	public static boolean checkedCross(int row, int col, int num, int[][] arrays){
		
		for(int k = 0; k < size; k++) {
			if(arrays[k][col] == num || arrays[row][k] == num) {
				return false;
			}
		}
		return true;
	}
	
	/*
	 * 박스안에 중복 값 찾기
	 */
	public static boolean checkedBox(int row, int col, int num, int[][] arrays) {
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				if(arrays[row + i][col + j] == num) {
					return false;
				}
			}
		}
		return true;
	}
	
	/*
	 * 빈 값 위치 찾기
	 */
	public static boolean isBlank(int[][] arrays) {
		
		for(int i = 0; i < size; i++) {
			for(int j = 0; j< size; j++) {
				if(arrays[i][j] == 0) {
					x = i;
					y = j;
					return false;
				}
			}
		}
		
		return true;
	}
	
	/*
	 * 스도쿠 출력
	 */
	public static void printSudoku(int[][] arrays) {
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < size; i++) {
			for(int j = 0; j< size; j++) {
				sb.append(arrays[i][j]);
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
}