[문제]
[풀이방법]
가로 / 세로 / 3*3 중 하나라도 조건(1-9 중 하나의 숫자만 존재해야한다)이 맞지 않으면 그대로 검증을 끝내고 다음 스도쿠 검증으로 넘어갑니다.
일단 1~9 까지의 숫자가 이전에 있었는지 확인하기 위해 boolean 배열을 생성했습니다.
7 3 6 4 2 9 5 8 1
5 8 9 1 6 7 3 2 4
2 1 4 5 8 3 6 9 7
8 4 7 9 3 6 1 5 2
1 5 3 8 4 2 9 7 6
9 6 2 7 5 1 8 4 3
4 2 1 3 9 8 7 6 5
3 9 5 6 7 4 2 1 8
6 7 8 2 1 5 4 3 9
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
T |
T | T |
T | T | T |
가로를 확인할 때 boolean 배열은 이런 식으로 이미 나온 숫자들의 인덱스에 해당하는 벨류를 T로 표시합니다.
나중에 같은 숫자가 나왔는데 이미 True라면 스도쿠가 아니기 때문에 검증을 종료합니다.
세로도 같은 방식으로 진행합니다.
문제는 3*3은 어떤 방식으로 해야할까입니다.
저는 위의 boolean 배열과 같은 방식인데 3*3이기 때문에 일차원 배열이 아닌 2차원 배열을 사용했습니다.
일단 3*3으로 나눠서 생각해야 하는데 3*3은
(1,1) (1,2) (1,3) / (1,4) (1,5) (1,6) /(1,7) (1,8) (1,9)
(2,1) (2,2) (2,3) / (2,4) (2,5) (2,6) /(2,7) (2,8) (2,9)
(3,1) (3,2) (3,3) / (3,4) (3,5) (3,6) /(3,7) (3,8) (3,9)
이렇게 같은 차원(?)으로 묶어줘야 합니다. 그래서 9개로 개수가 정해져있다는 특징을 이용했습니다.
가로의 인덱스에서 3으로 나눈 인덱스를 같은 차원으로 묶어줬습니다.
예를 들어, 가로 인덱스가 [2]라면 3으로 나눈 값은 0이 될 것입니다. [1] 또한 0이기 때문에 같은 차원으로 묶입니다.
하지만 [3]은 3으로 나누면 1이 되기 때문에 만약, 3으로 나누어떨어진다면 그 값을 1만큼 감소시켰습니다.
이제 1,2,3 / 4,5,6 / 7,8,9 가 같은 차원으로 묶였습니다.
그럼 위와 같은 방식으로 숫자의 중복을 검증합니다.
하지만 여기서 또 하나의 문제가 있습니다. 바로 3*3으로 검증해야할 칸이 9개라는 사실입니다.
그래서 세로 값이 3으로 나누어 떨어지면 check 이차원 배열을 초기화 해주었습니다.
설명과 코드를 보면서 차근 차근 이해해주세요
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
117
118
119
120
121
122
123
124
125
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static final int R = 10, C = 10;
static int[][] map;
static boolean[] number;
static boolean flag;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuffer sf = new StringBuffer();
int T = Integer.parseInt(st.nextToken());
for (int k = 0; k < T; k++) {
map = new int[R][C];
for (int i = 1; i < R; i++ ) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j < C; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int ans = 1;
for (int i = 1; i < R; i++) {
flag = true;
number = new boolean[10]; //1부터 9까지 있는 지 확인 (중복되면 false로 만든다. )
for (int j = 1; j < C; j++) {
if (number[map[i][j]]) {
flag= false;
break;
}
else {
number[map[i][j]] = true;
}
}
if (!flag) break;
}
if (flag) {
ans = 1;
}
else {
ans = 0;
}
if (ans == 0) {
continue;
}
for (int i = 1; i < R; i++) {
flag = true;
number = new boolean[10]; //1부터 9까지 있는 지 확인 (중복되면 false로 만든다. )
for (int j = 1; j < C; j++) {
if (number[map[j][i]]) {
flag= false;
break;
}
else {
number[map[j][i]] = true;
}
}
if (!flag) break;
}
if (flag) {
ans = 1;
}
else {
ans = 0;
}
if (ans == 0) {
continue;
}
int cnt = 0;
flag = true;
boolean[][] check = new boolean[3][10];
for (int i = 1; i < R; i++) {
if ((i-1) % 3 == 0) {
check = new boolean[3][10];
}
for (int j = 1; j < C; j++) {
int n = j/3;
if (j % 3 == 0) {
n--;
}
if (check[n][map[i][j]]) flag = false;
else {
check[n][map[i][j]] = true;
}
}
if (!flag) break;
}
if (flag) {
ans = 1;
}
else {
ans = 0;
}
}
System.out.println(sf.toString());
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'SWEA > D2' 카테고리의 다른 글
[SWEA 1959][D2][JAVA] 두 개의 숫자열 (0) | 2019.05.08 |
---|---|
[SWEA 1962][D2][JAVA] 숫자 배열 회전 (0) | 2019.05.07 |
[SWEA 1970][D2][JAVA] 쉬운 거스름돈 (0) | 2019.05.03 |
[SWEA 1979][D2][JAVA] 어디에 단어가 들어갈 수 있을까 (0) | 2019.05.02 |
[SWEA 1976][D2][JAVA] 시각덧셈 (0) | 2019.05.02 |