[백준] 백트래킹 - 2580번: 스도쿠 (Java)

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

2580번: 스도쿠

문제

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

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

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

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

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

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

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

입력

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

출력

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

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

나는 (1, 1) 부터 시작해서 한 행이 다 채워지면 다음 열을 탐색하는 방식으로 문제를 해결했다.

그래서 col == 9 가 되면 다음 열 0번째 행부터 탐색 했다. sudoku(row + 1, 0)

그리고 row == 9가 되면 모든 칸을 탐색한 것이므로 StringBuilder에 담아서 출력을 해주었다.

스도쿠 결과가 여러개 나올 수 있으므로 출력 후 System.exit(0) 로 프로그램을 종료했다.

isPossible 메서드는 숫자 i 가 해당 칸에 입력될 수 있는지를 판별하는 메서드이다.

행, 열 3 X 3 칸에 i가 있으면 false, 없으면 true를 리턴한다.

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 스도쿠
	public class Main {
	static int[][] arr = new int[9][9];
	static void input() throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	for (int i = 0; i < 9; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	for (int j = 0; j < 9; j++) {
	arr[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	}
	public static void main(String[] args) throws IOException {
	input();
	sudoku(0, 0);
	}
	static void sudoku(int row, int col) {
	if (col == 9) {
	sudoku(row + 1, 0);
	return;
	}
	if (row == 9) {
	StringBuilder sb = new StringBuilder();
	for (int[] ints : arr) {
	for (int anInt : ints) {
	sb.append(anInt).append(' ');
	}
	sb.append('\n');
	}
	System.out.println(sb);
	// 여러 경우의 수 중 하나만 출력해햐 함.
	System.exit(0);
	}
	if (arr[row][col] == 0) {
	for (int i = 1; i <= 9; i++) {
	if (isPossible(row, col, i)) {
	arr[row][col] = i;
	sudoku(row, col + 1);
	}
	}
	arr[row][col] = 0;
	return;
	}
	sudoku(row, col + 1);
	} // sudoku()
	static boolean isPossible(int row, int col, int value) {
	// 같은 행
	for (int i = 0; i < 9; i++) {
	if (arr[row][i] == value) {
	return false;
	}
	}
	// 같은 열
	for (int i = 0; i < 9; i++) {
	if (arr[i][col] == value) {
	return false;
	}
	}
	// 3 * 3 정사각형 칸 체크
	int rec_row = (row / 3) * 3;
	int rec_col = (col / 3) * 3;
	for (int i = rec_row; i < rec_row + 3; i++) {
	for (int j = rec_col; j < rec_col + 3; j++) {
	if (arr[i][j] == value) {
	return false;
	}
	}
	}
	return true;
	}
	}

view raw A2580.java hosted with ❤ by GitHub

참고한 글: https://st-lab.tistory.com/119