반응형
- 알고리즘 분류 : DFS/구현
- 사용 언어 : JAVA
소스 설명은 주석을 참고해주세요.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int[][] map = new int[9][9];
public static void main(String[] args) 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++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
Sudoku(0,0);
}
public static void Sudoku(int y, int x) {
if(x == 9) {
Sudoku(y+1, 0);
return;
}
if(y == 9) {
StringBuilder sb = new StringBuilder();
for(int i=0; i<9; i++) {
for(int j=0; j<9; j++) {
sb.append(map[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb.toString());
System.exit(0); // 시스템을 종료해야함. 안그러면 중복 출력 가능
}
if(map[y][x] == 0) {
for(int i=1; i<=9; i++) {
if(check(y, x, i)) {
map[y][x] = i;
Sudoku(y, x+1);
}
}
map[y][x] = 0; // 백트래킹. 다시 돌려둠.
return;
}
Sudoku(y, x+1);
}
// 검사
public static boolean check(int y, int x, int num) {
// 1. 가로줄 검사
for(int i=0; i<9; i++) {
if(map[y][i] == num) {
return false;
}
}
// 2. 세로줄 검사
for(int i=0; i<9; i++) {
if(map[i][x] == num) {
return false;
}
}
// 3. 3x3 검사
int initY = (y / 3) * 3;
int initX = (x / 3) * 3;
for (int i = initY; i < initY + 3; i++) {
for (int j = initX; j < initX + 3; j++) {
if (map[i][j] == num) {
return false;
}
}
}
return true;
}
}
반응형
'Algorithm' 카테고리의 다른 글
[BAEKJOON] 7569번 : 토마토 (JAVA) (1) | 2024.02.18 |
---|---|
[BAEKJOON] 14284번 : 간선 이어가기 2 (JAVA) (0) | 2024.01.07 |
[Programmers] 택배 배달과 수거하기 (Java) (0) | 2023.09.17 |
[BAEKJOON] 2109번 : 순회강연 (JAVA) (0) | 2023.08.19 |
[BAEKJOON] 1339번 : 단어 수학 (JAVA) (0) | 2023.08.13 |