728x90
https://www.acmicpc.net/problem/2580
1. ArrayList에 빈칸 정보를 넣는다.
2. 1~9까지 포문을 돌면서 행,열, 3*3 배열에서 해당 값으로 세팅해도 되는지 확인한다.
된다면 arr배열에 해당 값으로 세팅하고, list의 다음 빈칸으로 넘어간다.
안된다면 arr배열에 0으로 세팅하고, 다음 숫자로 넘어간다.
3. 그렇게 list의 마지막까지 세팅할 값을 찾았다면 print~~
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int[][] arr = new int[9][9];
static ArrayList<Node> list = new ArrayList<>();
static class Node {
int x, y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int i = 0; i < 9; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 0) //빈칸은 list에 넣기
list.add(new Node(i, j));
}
}
check(0,list.get(0).x,list.get(0).y); //list의 첫번째 빈칸으로 시작
}
static void print() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(arr[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
System.exit(0);
}
static void check(int idx,int x, int y) {
for (int i = 1; i <= 9; i++) {
if (possible(x, y, i)) {
arr[x][y] = i;
if(idx==list.size()-1) {
print();
}
else check(idx+1,list.get(idx+1).x,list.get(idx+1).y);
}
arr[x][y]=0;
}
}
static boolean possible(int x, int y, int value) {
// 행
for (int i = 0; i < 9; i++) {
if (arr[x][i] == value)
return false;
}
// 열
for (int i = 0; i < 9; i++) {
if (arr[i][y] == value)
return false;
}
// 9칸
int row = x/3*3;
int col = y/3*3;
for (int i = row; i < row+3; i++) {
for (int j = col; j < col+3; j++) {
if (arr[i][j] == value)
return false;
}
}
return true;
}
}
'Java' 카테고리의 다른 글
[백준 1300] K번째 수 (JAVA) (0) | 2023.05.05 |
---|---|
[백준 1238] 파티 (JAVA) (0) | 2023.05.04 |
[백준 2493] 탑 (JAVA) (0) | 2023.05.02 |
[백준 15663] N과 M (9) (JAVA) (0) | 2023.05.02 |
[백준 15657] N과 M(8) (JAVA) (0) | 2023.05.01 |