👀 문제
https://www.acmicpc.net/problem/2580
👊 도전
1. 설계
- dfs로 빈칸에 숫자를 지정해준 뒤, 열, 행, 3*3행렬에서 조건이 만족하는지 확인한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int[][] map;
static ArrayList<Node> list;
public static void dfs(int idx) {
if(idx==list.size()) {
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
System.exit(0);
}
Node node=list.get(idx);
for(int i=1;i<=9;i++) {
map[node.x][node.y]=i;
if(checkRow(node) && checkColumn(node) && checkBox(node))
dfs(idx+1);
if(i==9) map[node.x][node.y]=0;
}
}
public static boolean checkRow(Node node) {
int x=node.x;
int y=node.y;
for(int i=0;i<9;i++) {
if(i==y) continue;
if(map[x][i]==map[x][y]) return false;
}
return true;
}
public static boolean checkColumn(Node node) {
int x=node.x;
int y=node.y;
for(int i=0;i<9;i++) {
if(i==x) continue;
if(map[i][y]==map[x][y]) return false;
}
return true;
}
public static boolean checkBox(Node node) {
int x=node.x;
int y=node.y;
int a=x/3*3;
int b=y/3*3;
for(int i=a;i<a+3;i++) {
for(int j=b;j<b+3;j++) {
if(i==x && j==y) continue;
if(map[i][j]==map[x][y]) return false;
}
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
map=new int[9][9];
list=new ArrayList<>();
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
map[i][j]=scan.nextInt();
if(map[i][j]==0) list.add(new Node(i, j));
}
}
dfs(0);
}
}
class Node{
int x;
int y;
public Node(int x, int y) {
this.x=x;
this.y=y;
}
}
3. 결과
🤟 성공 🤟
빈칸에 만족하는 숫자가 없을 때의 예외처리를 해주지 않아서 실패했었다.
4. 설명
- 빈칸 위치를 ArrayList에 저장한다
- scan해서 받아오는 과정에서 0은 해당 위치를 AraryList에 저장한다.
- x, y좌표를 저장하기 위해 Node클래스를 선언하여 이용한다.
- DFS를 이용한다
- 빈칸에 for문을 통해 1~9중 하나를 부여한다.
- 해당 위치에 넣은 숫자가 행, 열, 박스에서 조건을 만족하는지 확인한다.
- 만족한다면, dfs(idx+1)로 재귀를 호출하여 다음 빈칸을 확인한다.
- 만족하지 않는다면 다음 숫자를 넣어 계속 확인한다.
- 9까지 확인하였는데도 만족하지 않는다면, 0으로 다시 리셋한다. 이 경우 어짜피 ArrayList의 마지막 인덱스까지 확인하지 못하게 되므로 정답에서 자연스럽게 제외된다.
- 행, 열, 박스 조건을 확인한다
- checkRow()로 현재 행에서 중복되는 숫자는 없는지 확인한다.
- checkColumn()은 현재 열에서 중복되는 숫자가 없는지 확인한다.
- checkBox()는 3*3행렬에서 확인한다. 이때 i, j의 시작점을 계산해야하는데, 시작점은 0, 3, 6으로 3의 배수이므로 3의 배수로 만들기 위해 /3 *3을 해준다.
👏 해결 완료!
참고
- [백준,BOJ 2580] 스도쿠 (JAVA 구현) https://fbtmdwhd33.tistory.com/41