설명
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.
위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.
입력
9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.
출력
9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.
예시 입력
예시 출력
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
JavaScript
복사
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
JavaScript
복사
풀이 과정
백트래킹은 말그대로 가능한 모든 조합을 찾아내면서 문제를 푸는 알고리즘 기법입니다.
문제에서 주어진 입력에서 우리가 할 것은 빈칸, 즉 0에 적절한 숫자를 집어넣는 것입니다.
문제를 풀며 총 두 개의 함수를 사용했는데, 백트래킹을 시행하는 함수와 빈 칸에 해당하는 숫자가 들어갈 수 있는지 확인하는 함수입니다.
예를 들어, 첫 번째 줄에 103... 에 적절한 숫자를 집어넣는다고 가정합시다.
가로, 세로, 그리고 3X3 칸 안에서 중복되는 숫자를 제외한 나머지 숫자를 집어 넣으며 조합을 이어 나갑니다.
최종 코드
package baekjoon.back_tracking;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class _2239 {
static final int BOARD_SIZE = 9;
static int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < BOARD_SIZE; i++) {
String input = br.readLine();
for (int j = 0; j < BOARD_SIZE; j++) {
board[i][j] = Character.getNumericValue(input.charAt(j));
}
}
backtracking();
}
private static void backtracking() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
if (isAvaliableNumber(i, j, k)) {
board[i][j] = k;
backtracking();
board[i][j] = 0;
}
}
return; // 빈 칸에 숫자를 채우지 못하면 되돌아감
}
}
}
printBoard();
System.exit(0); // 첫 번째 해를 찾으면 프로그램 종료
}
private static void printBoard() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
System.out.print(board[i][j]);
}
System.out.println();
}
}
public static boolean isAvaliableNumber(int x, int y, int number) {
for (int i = 0; i < BOARD_SIZE; i++) {
if (x == i) {
continue;
}
if (board[i][y] == number) {
return false;
}
}
for (int i = 0; i < BOARD_SIZE; i++) {
if (y == i) {
continue;
}
if (board[x][i] == number) {
return false;
}
}
int startX = (x / 3) * 3;
int startY = (y / 3) * 3;
for (int i = startX; i < startX + 3; i++) {
for (int j = startY; j < startY + 3; j++) {
if (board[i][j] == number) {
return false;
}
}
}
return true;
}
}
JavaScript
복사
