링크
https://www.acmicpc.net/problem/2580
문제 설명
정답률 27.057%
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력 예제
- 아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다.
- 스도쿠 판의 빈 칸의 경우에는 0이 주어진다.
- 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0
출력 예제
- 모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
- 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1
풀이
9X9의 스도쿠 판에서 (0, 0) 좌표부터 시작하여 백트래킹을 진행한다. 값이 0이라면 1~9 중에서 가능한 수를 탐색하는데 같은 행, 같은 열 그리고 같은 박스내에 중복되는 수가 없을 때 해당 값을 저장한다.
//스도쿠의 값이 0이라면 1~9 중에서 가능한 수 탐색
if (sudoku[row][col] == 0) {
for (int i = 1; i <= SUDOKU_SIZE; i++) {
if (possibility(row, col, i)) {
sudoku[row][col] = i;
backTracking(row, col + 1);
sudoku[row][col] = 0; //재귀 호출 뒤 원복
}
}
}
//0이 아니라면 다음 열을 기준으로 재귀 호출
else {
backTracking(row, col + 1);
}중복되는 수가 있는지는 다음과 같이 판단한다.
static boolean possibility(int row, int col, int val) {
//val이 같은 행에 존재하는지 검사
for (int i = 0; i < SUDOKU_SIZE; i++) {
if (sudoku[row][i] == val) {
return false;
}
}
//val이 같은 열에 존재하는지 검사
for (int i = 0; i < SUDOKU_SIZE; i++) {
if (sudoku[i][col] == val) {
return false;
}
}
//3x3 칸의 첫 번째 좌표 설정
int setRow = (row / 3) * 3;
int setCol = (col / 3) * 3;
//val이 3x3 칸에 존재하는지 검사
for (int i = setRow; i < setRow + 3; i++) {
for (int j = setCol; j < setCol + 3; j++) {
if (sudoku[i][j] == val) {
return false;
}
}
}
//중복되는 값이 존재하지 않을 경우
return true;
}재귀를 호출하면서 현재 행을 다 채웠을 경우 다음 행을 기준으로 재귀를 호출하며 모든 행을 다 채웠을 경우 스도쿠 결과 값을 출력한다.
//행을 다 채웠을 경우 다음 행을 기준으로 재귀 호출
if (col == SUDOKU_SIZE) {
backTracking(row + 1, 0);
return;
}
//모든 행을 다 채웠을 경우 출력 후 종료
if (row == SUDOKU_SIZE) {
for (int i = 0; i < SUDOKU_SIZE; i++) {
for (int j = 0; j < SUDOKU_SIZE; j++) {
sb.append(sudoku[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
System.exit(0);
}코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
//백준
public class Main {
static final int SUDOKU_SIZE = 9;
static int[][] sudoku = new int[SUDOKU_SIZE][SUDOKU_SIZE];
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < SUDOKU_SIZE; i++) {
sudoku[i] = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
backTracking(0, 0);
}
static void backTracking(int row, int col) {
//행을 다 채웠을 경우 다음 행을 기준으로 재귀 호출
if (col == SUDOKU_SIZE) {
backTracking(row + 1, 0);
return;
}
//모든 행을 다 채웠을 경우 출력 후 종료
if (row == SUDOKU_SIZE) {
for (int i = 0; i < SUDOKU_SIZE; i++) {
for (int j = 0; j < SUDOKU_SIZE; j++) {
sb.append(sudoku[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
System.exit(0);
}
//스도쿠의 값이 0이라면 1~9 중에서 가능한 수 탐색
if (sudoku[row][col] == 0) {
for (int i = 1; i <= SUDOKU_SIZE; i++) {
if (possibility(row, col, i)) {
sudoku[row][col] = i;
backTracking(row, col + 1);
sudoku[row][col] = 0; //재귀 호출 뒤 원복
}
}
}
//0이 아니라면 다음 열을 기준으로 재귀 호출
else {
backTracking(row, col + 1);
}
}
static boolean possibility(int row, int col, int val) {
//val이 같은 행에 존재하는지 검사
for (int i = 0; i < SUDOKU_SIZE; i++) {
if (sudoku[row][i] == val) {
return false;
}
}
//val이 같은 열에 존재하는지 검사
for (int i = 0; i < SUDOKU_SIZE; i++) {
if (sudoku[i][col] == val) {
return false;
}
}
//3x3 칸의 첫 번째 좌표 설정
int setRow = (row / 3) * 3;
int setCol = (col / 3) * 3;
//val이 3x3 칸에 존재하는지 검사
for (int i = setRow; i < setRow + 3; i++) {
for (int j = setCol; j < setCol + 3; j++) {
if (sudoku[i][j] == val) {
return false;
}
}
}
//중복되는 값이 존재하지 않을 경우
return true;
}
}
백엔드