문제링크 : https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3
www.acmicpc.net
단순하게만 생각한다면, '빈 칸이 포함되는 가로줄, 세로줄, 9개의 네모 칸 안의 수를 다 비교해서, 빈칸에 넣을 수 있는 수를 넣으면 되는 거 아닌가?'라고 생각할 수 있다. 이것도 틀린 말은 아니나 소싯적(?) 스도쿠를 조금이라도 해본 사람은 이게 그렇게 간단한 문제는 아니라는 걸 알 것이다. 다 비교해봐도 빈 칸 안에 넣을 수 있는 수가 1개가 넘는 경우가 많기 때문이다. 심지어 이 문제에는 '판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.'라는 조건이 있다. 그 말은 81개의 모든 칸이 0으로 주어진다고 해도 답이 나와야한다는 얘기다. 뭔가 완전 탐색의 냄새(?)가 나지 않는가?ㅋㅋ 풀이에 대한 설명을 시작하겠다. 일단 이 풀이는 DFS 백트래킹이며, 자세한 건 코드를 보고 설명하는 편이 나을 듯하다.
|
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static boolean finished = false;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][] puzzle = new int[9][9];
List<Point> zeroList = new ArrayList<Point>();
for(int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < 9; j++) {
puzzle[i][j] = Integer.parseInt(st.nextToken());
if(puzzle[i][j] == 0) {
zeroList.add(new Point(i, j));
}
}
}
} else {
printPuzzle(puzzle);
}
}
private static void dfs(Point point, int[][] puzzle, List<Point> zeroList, int depth) {
if(finished) {
return;
}
boolean[] checked = getCandidates(puzzle, point);
for(int k = 1; k <= 9; k++) {
if(!checked[k]) {
puzzle[i][j] = k;
printPuzzle(puzzle);
finished = true;
return;
}
puzzle[i][j] = 0;
}
}
}
private static void printPuzzle(int[][] puzzle) {
StringBuffer sb = new StringBuffer();
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
}
sb.append("\n");
}
System.out.println(sb);
}
private static boolean[] getCandidates(int[][] puzzle, Point point) {
boolean[] checked = new boolean[10];
for(int k = 0; k < 9; k++) {
checked[puzzle[i][k]] = true;
}
for(int k = 0; k < 9; k++) {
checked[puzzle[k][j]] = true;
}
int sI = i / 3 * 3;
int sJ = j / 3 * 3;
for(int k = sI; k < sI + 3; k++) {
for(int h = sJ; h < sJ + 3; h++) {
checked[puzzle[k][h]] = true;
}
}
return checked;
}
private static class Point {
private int i;
private int j;
public Point(int i, int j) {
this.i = i;
this.j = j;
}
public int getI() {
return i;
}
public int getJ() {
return j;
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
1. 빈 칸의 위치를 모두 List에 저장한다.
2. 첫번째 빈 칸에 들어갈 수 있는 모든 수를 구한 후, 하나씩 넣은 후, DFS로 다음 빈 칸으로 이동한다.
3. 다음 빈 칸에 대해서도 동일하게(재귀함수) 들어갈 수 있는 모든 수를 구한 후, 하나씩 넣고 다음 칸으로 이동한다.
4. 만약 List에 저장되있는 모든 빈 칸에 대해 숫자가 채워졌다면 함수 실행을 멈추고 값을 출력한다.
5. 만약 현재 넣어본 수가 스도쿠의 조건을 만족할 수 없는 수라면, DFS를 도는 어느 순간, 해당 빈 칸에 들어갈 수 있는 수가 0개로 나올 것이고 해당 조건은 모든 빈 칸을 채울 수 없을 것이다. 해당 depth를 충족시킬 수 없을 것이다.
6. 아까 빈 칸에 들어갈 수 있는 여러가지 수 중 하나를 일단 넣어봤다. 다른 경우의 수도 알아보려면 아까 수를 넣기 이전 상태로 초기화가 되어야한다. 칸을 다시 빈 칸(0)으로 초기화해준다.(백트래킹)
근데 상위권 풀이에 비해 실행시간이 다소 길다...-_- 상위권 풀이를 살펴보니, 굳이 빈칸에 넣을 수 있는 수를 매번 구할 필요가 없다라는 걸 깨달았다. 코드는 아래와 같다.
|
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static boolean finished = false;
private static boolean[][] checkI = new boolean[9][10];
private static boolean[][] checkJ = new boolean[9][10];
private static boolean[][][] checkBox = new boolean[3][3][10];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][] puzzle = new int[9][9];
List<Point> zeroList = new ArrayList<Point>();
for(int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < 9; j++) {
puzzle[i][j] = Integer.parseInt(st.nextToken());
if(puzzle[i][j] == 0) {
zeroList.add(new Point(i, j));
} else {
checkI[i][puzzle[i][j]] = true;
checkJ[j][puzzle[i][j]] = true;
checkBox[i / 3][j / 3][puzzle[i][j]] = true;
}
}
}
} else {
printPuzzle(puzzle);
}
}
private static void dfs(Point point, int[][] puzzle, List<Point> zeroList, int depth) {
if(finished) {
return;
}
for(int k = 1; k <= 9; k++) {
if(!checkI[i][k] && !checkJ[j][k] && !checkBox[i / 3][j / 3][k]) {
puzzle[i][j] = k;
checkI[i][k] = true;
checkJ[j][k] = true;
checkBox[i / 3][j / 3][k] = true;
printPuzzle(puzzle);
finished = true;
return;
}
puzzle[i][j] = 0;
checkI[i][k] = false;
checkJ[j][k] = false;
checkBox[i / 3][j / 3][k] = false;
}
}
}
private static void printPuzzle(int[][] puzzle) {
StringBuffer sb = new StringBuffer();
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
}
sb.append("\n");
}
System.out.println(sb);
}
private static class Point {
private int i;
private int j;
public Point(int i, int j) {
this.i = i;
this.j = j;
}
public int getI() {
return i;
}
public int getJ() {
return j;
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'알고리즘' 카테고리의 다른 글
| 백준(BOJ) 1525 : 퍼즐 (JAVA) (0) | 2020.02.14 |
|---|---|
| 백준(BOJ) 1107 : 리모컨 (JAVA) (0) | 2020.02.13 |
| 백준(BOJ) 2186 : 문자판 (JAVA) (0) | 2020.02.11 |
| 백준(BOJ) 11053 : 가장 긴 증가하는 부분 수열 (JAVA) (0) | 2020.02.11 |
| 백준(BOJ) 1451 : 직사각형으로 나누기 (JAVA) (0) | 2020.02.10 |
