2239번: 스도쿠
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다
www.acmicpc.net
백트래킹 기본문제 중 하나입니다.
우선 스도쿠는 9 * 9 배열이 있을 때 각 행, 열, 3 * 3구간에서 1 ~ 9가 한 번씩만 나오게 하는 문제입니다.
그럼 각 행, 열, 구간을 중복체크하는 배열을 세개 사용합니다.
(0, 0)부터 (8, 8)까지 한 칸씩 확인하며, list[x][y] != 0이면 수를 넣을 필요가 없으므로 바로 다음좌표를 탐색합니다.
list[x][y] == 0이면 1 ~ 9까지 넣을 수 있는지 확인합니다.
(x, y)에서 숫자 i가 x행에서 사용되었는지, y열에서 사용되었는지, 같은 구간에서 사용되었는지 각각 확인해줍니다.
세 구간 모두 사용되지 않은 숫자만 list[x][y]에 넣어주고 다음좌표로 넘겨줍니다.
모든 좌표를 탐색하였으면 답을 출력하고 리턴합니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static char div[][] = { { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' },
{ 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' }, { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' },
{ 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' },
{ 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' },
{ 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, };
static boolean rowsChk[][] = new boolean[10][10];
static boolean colsChk[][] = new boolean[10][10];
static boolean divChk[][] = new boolean[10][10];
static int list[][] = new int[10][10];
static boolean func(int x, int y) {
if (x == 9) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(list[i][j]);
}
sb.append("\n");
}
System.out.println(sb.toString());
return true;
}
int nx = x;
int ny = y + 1;
if (ny == 9) {
nx++;
ny = 0;
}
if (list[x][y] != 0)
return func(nx, ny);
else {
for (int i = 1; i <= 9; i++) {
if (rowsChk[x][i] || colsChk[y][i] || divChk[div[x][y] - 'a'][i])
continue;
rowsChk[x][i] = true;
colsChk[y][i] = true;
divChk[div[x][y] - 'a'][i] = true;
list[x][y] = i;
boolean chk = func(nx, ny);
if (chk)
return true;
list[x][y] = 0;
divChk[div[x][y] - 'a'][i] = false;
colsChk[y][i] = false;
rowsChk[x][i] = false;
}
}
return false;
}
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
char ch[];
for (int i = 0; i < 9; i++) {
st = new StringTokenizer(br.readLine());
ch = st.nextToken().toCharArray();
for (int j = 0; j < 9; j++) {
list[i][j] = ch[j] - '0';
if (list[i][j] != 0) {
rowsChk[i][list[i][j]] = true;
colsChk[j][list[i][j]] = true;
divChk[div[i][j] - 'a'][list[i][j]] = true;
}
}
}
}
public static void main(String[] args) throws Exception {
input();
func(0, 0);
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 19236 청소년 상어 (0) | 2021.04.22 |
|---|---|
| boj 2458 키 순서 (0) | 2021.04.13 |
| boj 14889 스타트와 링크 (0) | 2021.03.17 |
| boj 2023 신기한 소수 (0) | 2021.03.16 |
| boj 14500 테트로미노 (0) | 2021.03.15 |