백준 2239번 : 스도쿠

[레벨5]

 

· 문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

· 입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

 

· 출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

· 제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++17: 180ms
  • Java 15: 528ms
  • PyPy3: 2064ms

 

· 풀이

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

public class Main {
	
	static int[][] arr = new int[9][9];
	static boolean flag;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		//초기화.
		for (int i = 0; i < 9; i++) {
			char[] c = br.readLine().toCharArray();
			for (int j = 0; j < 9; j++) {
				arr[i][j] = c[j] - '0';
			}
		}

		//스도쿠 검사 실시.
		sudoku(0);
		
		//출력할 스도쿠 정렬.
		for (int[] a : arr) {
			for (int b : a) {
				sb.append(b);
			}
			sb.append("\n");
		}

		System.out.println(sb.toString());
	}

	private static void sudoku(int d) {

		if (d == 81) {
			flag = true;
			return;
		}

		int r = d / 9;	//행
		int c = d % 9;	//열

		if (arr[r][c] != 0)
			sudoku(d + 1);
		else {
			for (int i = 1; i < 10; i++) {
				if (!isValid(r, c, i))
					continue;
				arr[r][c] = i;
				sudoku(d + 1);

				// 종료 조건이 아니라면 더이상 선택할 수가 없다는 뜻 => 백트랙킹
				if (flag)
					return;
				arr[r][c] = 0;

			}
		}

	}
	
	//가로, 세로, 면 검사.
	private static boolean isValid(int r, int c, int n) {

		for (int i = 0; i < 9; i++) {
			if (arr[i][c] == n || arr[r][i] == n)
				return false;
		}

		int sr = r / 3 * 3;
		int sc = c - c % 3;
		for (int row = sr; row < sr + 3; row++) {
			for (int col = sc; col < sc + 3; col++) {
				if (arr[row][col] == n)
					return false;
			}
		}
		return true;
	}
}