[JAVA] 백준 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

 

 

📋 코드

import java.util.*;
public class Main {
	
	static int cnt = 0; // 빈 곳 개수
	static int sudoku[][] = new int[10][10];
	static int mark[][] = new int[82][2];
	static boolean flag = false;
	
	public static void Backtracking(int n) {
		
		if(n == cnt+1) {
			for (int i = 1; i <= 9; i++) {
				for (int j = 1; j <= 9; j++) {
					System.out.print(sudoku[i][j]+" ");
				}
				System.out.println();
			}
			flag = true;
			return;
		}
		
		int x = mark[n][0];
		int y = mark[n][1];
		int sx = (x-1)/3*3+1;
		int sy = (y-1)/3*3+1;
		boolean check[] = new boolean[10];
		
		// 행, 열 체크
		for (int i = 1; i <= 9; i++) {
			check[sudoku[x][i]] = check[sudoku[i][y]] = true;
		}
		
		// 3x3 사각형 체크
		for (int i = sx; i < sx+3; i++) {
			for (int j = sy; j < sy+3; j++) {
				check[sudoku[i][j]] = true;
			}
		}
		
		for (int i = 1; i <= 9; i++){
			if(!check[i]) {
				sudoku[x][y] = i;
				Backtracking(n+1);
				if(flag) return; 
				sudoku[x][y] = 0;
			}
		}
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				int x = sc.nextInt();
				sudoku[i][j] = x;
				if(x == 0) {
					cnt++;
					mark[cnt][0] = i;
					mark[cnt][1] = j;
				}
			}
		}
		Backtracking(1);
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

 

백트래킹(backtracking)은 퇴각 검색이라는 의미로 탐색을 하는 도중 막히면 되돌아가서 다시 답을 탐색하는 기법을 의미합니다. DFS의 경우 가능한 모든 경로를 탐색하므로 DFS에 조건을 놓고 가지를 쳐가면서 불필요한 경로를 차단하고 정답으로 향하게 하는 것이 백트래킹입니다.

위 문제에서는 스도쿠 공백에 숫자를 채워나가는데, 모든 공백을 올바르게 채우지 못하고 도중에 막히게 된다면 그 이상 탐색하지 않고 퇴각하여 다른 경우의 수를 탐색하여 답을 찾습니다.

 

sudoku[10][10] 배열은 (1,1)에서 시작해서 (9,9)까지 스도쿠 숫자들을 저장합니다.

그리고 mark[82][2] 배열은 공백의 좌표들을 저장합니다.

 

Backtracking() 함수에서

int x = mark[n][0];
int y = mark[n][1];
int sx = (x-1)/3*3+1;
int sy = (y-1)/3*3+1;
boolean check[] = new boolean[10];

x, y는 공백의 좌표, 그리고 sx, sy는 3x3으로 구역을 나눴을 때의 구역의 시작 좌표를 의미합니다.

예를 들어 x, y 가 (5,5)라면 sx, sy는 (4,4)가 됩니다.

 

1. 현재 행, 열에서 숫자 체크  

// 행, 열 체크
for (int i = 1; i <= 9; i++) {
	check[sudoku[x][i]] = check[sudoku[i][y]] = true;
}

(1,1) 기준으로
같은 행에 3,5,4,6,9,2,7,8
같은 열에 7,3,8,5,9,6,2

그렇다면 check배열은 아래와 같이 저장됩니다.

arr	check[1]	check[2]	check[3]	check[4]	check[5]	check[6]	check[7]	check[8]	check[9]
boolean	false	true	true	true	true	true	true	true	true

 

2. 현재 구역에서 숫자 체크  

// 3x3 사각형 체크
for (int i = sx; i < sx+3; i++) {
	for (int j = sy; j < sy+3; j++) {
		check[sudoku[i][j]] = true;
	}
}

(1,1)이 속한 구역 기준으로 3,5,7,8,2,6

check배열은 아래와 같이 저장됩니다.

arr	check[1]	check[2]	check[3]	check[4]	check[5]	check[6]	check[7]	check[8]	check[9]
boolean	false	true	true	true	true	true	true	true	true

 

3. check배열에 체크가 안된 숫자를 스도쿠에 채워 넣고 재귀 함수를 호출합니다.

for (int i = 1; i <= 9; i++){
	if(!check[i]) {
		sudoku[x][y] = i;
		Backtracking(n+1);
		if(flag) return; 
		sudoku[x][y] = 0;
	}
}

 

 

4. 스도쿠에 수를 모두 채워 넣었다면 스도쿠 출력 후 함수 종료

if(n == cnt+1) {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			System.out.print(sudoku[i][j]+" ");
		}
		System.out.println();
	}
	flag = true;
	return;
}

만약 정답을 구했다면 flag에 true값을 줘서 다른 재귀 함수들에서 추가적인 탐색을 하지 않도록 하여 시간 초과를 피합니다.

 

 

 

🔗 링크

https://www.acmicpc.net/problem/2580

2580번: 스도쿠