BOJ_2239_스도쿠_JAVA
문제 : 스도쿠
링크 : BOJ_2239_스도쿠
접근 방식
스도쿠 규칙에 맞게 수를 채워넣어야 하는 문제이다.
조건으로써 완성되는 스도쿠의 답이 여러 개 있다면 사전 순으로 앞서는 스도쿠 완성 결과를 출력해야한다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ_2239_스도쿠 {
static char[][] sudoku;
static String answer = "";
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
sudoku = new char[9][9];
for (int i = 0; i < 9; i++) {
sudoku[i] = in.readLine().toCharArray();
}
dfs(0, 0);
System.out.println(answer);
}
public static void dfs(int x, int y) {
if (y == 9) {
StringBuilder sb = new StringBuilder();
String[] str = answer.split("\n");
for(int i=0;i<9;i++) {
sb.append(sudoku[x][i]);
}
if(answer != "" && str[x].compareTo(sb.toString()) < 0 ) {
return;
}
dfs(x + 1, 0);
return;
}
if (x == 9) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(sudoku[i][j]);
}
sb.append("\n");
}
if (answer.compareTo(sb.toString()) < 0) {
answer = sb.toString();
}
return;
}
if (sudoku[x][y] == '0') {
for (int i = 1; i <= 9; i++) {
if (check(x, y, i + '0')) {
sudoku[x][y] = (char) (i + '0');
dfs(x,y+1);
}
}
sudoku[x][y] = '0';
return;
}
dfs(x, y + 1);
}
static boolean check(int x, int y, int value) {
// 같은 열
for (int i = 0; i < 9; i++) {
if (sudoku[x][i] == value) {
return false;
}
}
// 같은 행
for (int i = 0; i < 9; i++) {
if (sudoku[i][y] == value) {
return false;
}
}
int xx = (x / 3) * 3;
int yy = (y / 3) * 3;
for (int i = xx; i < xx + 3; i++) {
for (int j = yy; j < yy + 3; j++) {
if (sudoku[i][j] == value) {
return false;
}
}
}
return true;
}
}
dfs를 통해 탐색하며 스도쿠 조건을 계속해서 체크하는 부분을 구현하는 것이 어려웠던 것 같다.