https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Psz16AYEDFAUq
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제 접근
무식하게 풀었다.
스도쿠는 가로, 세로, 3X3 크기의 정사각형 안에서 1~9의 숫자가 겹치지 않아야 한다.
정사각형의 경우
[0][0], [0][3], [0][6]
[3][0], [3][3], [3][6]
[6][0], [6][3], [6][6]
9개의 꼭짓점을 기준으로 같은 정사각형 내에 있는 다른 8개의 숫자와 비교한다.
가로, 세로의 경우는 인덱스의 0~9, 1~9, 2~9 ... 이렇게 모든 수를 다 일일이 비교하였다.
위에서 차례대로 검사해가기 때문에 한 곳이라도 같은 수가 나오면 바로 다음 테스트 케이스를 검사하기 위해 flag를 활용
import java.util.*;
import java.io.*;
public class Solution{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int t=0; t<T; t++) {
String[][] sudoku = new String[9][9];
// StringTokenizer st = new StringTokenizer(br.readLine()); 여기서 한 번에 입력값을 넣으면 오류뜬다. 9X9를 한 번에 넣어서 그런건가?
for(int i=0; i<9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine()); // 여기선 입력값을 한 번에 넣어도 오류가 안뜨고 배열에 값이 잘 들어간다 왤까?
for(int j=0; j<9; j++) {
sudoku[i][j] = st.nextToken();
}
}
boolean flag = false;
// 네모 검증
for(int i=1; i<9; i++) {
// 0, 0
if(sudoku[0][0].equals(sudoku[0][1]) || sudoku[0][0].equals(sudoku[0][2])
|| sudoku[0][0].equals(sudoku[1][0]) || sudoku[0][0].equals(sudoku[1][1]) || sudoku[0][0].equals(sudoku[1][2])
|| sudoku[0][0].equals(sudoku[2][0]) || sudoku[0][0].equals(sudoku[2][1]) || sudoku[0][0].equals(sudoku[2][2])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
// 0, 3
if(sudoku[0][3].equals(sudoku[0][4]) || sudoku[0][3].equals(sudoku[0][5])
|| sudoku[0][3].equals(sudoku[1][3]) || sudoku[0][3].equals(sudoku[1][4]) || sudoku[0][3].equals(sudoku[1][5])
|| sudoku[0][3].equals(sudoku[2][3]) || sudoku[0][3].equals(sudoku[2][4]) || sudoku[0][3].equals(sudoku[2][5])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
// 0, 6
if(sudoku[0][6].equals(sudoku[0][7]) || sudoku[0][6].equals(sudoku[0][8])
|| sudoku[0][6].equals(sudoku[1][6]) || sudoku[0][6].equals(sudoku[1][7]) || sudoku[0][6].equals(sudoku[1][8])
|| sudoku[0][6].equals(sudoku[2][6]) || sudoku[0][6].equals(sudoku[2][7]) || sudoku[0][6].equals(sudoku[2][8])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
// 3, 0
if(sudoku[3][0].equals(sudoku[3][1]) || sudoku[3][0].equals(sudoku[3][2])
|| sudoku[3][0].equals(sudoku[4][0]) || sudoku[3][0].equals(sudoku[4][1]) || sudoku[3][0].equals(sudoku[4][2])
|| sudoku[3][0].equals(sudoku[5][0]) || sudoku[3][0].equals(sudoku[5][1]) || sudoku[3][0].equals(sudoku[5][2])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
// 3, 3
if(sudoku[3][3].equals(sudoku[3][4]) || sudoku[3][3].equals(sudoku[3][5])
|| sudoku[3][3].equals(sudoku[4][3]) || sudoku[3][3].equals(sudoku[4][4]) || sudoku[3][3].equals(sudoku[4][5])
|| sudoku[3][3].equals(sudoku[5][3]) || sudoku[3][3].equals(sudoku[5][4]) || sudoku[3][3].equals(sudoku[5][5])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
// 3, 6
if(sudoku[3][6].equals(sudoku[3][7]) || sudoku[3][6].equals(sudoku[3][8])
|| sudoku[3][6].equals(sudoku[4][6]) || sudoku[3][6].equals(sudoku[4][7]) || sudoku[3][6].equals(sudoku[4][8])
|| sudoku[3][6].equals(sudoku[5][6]) || sudoku[3][6].equals(sudoku[5][7]) || sudoku[3][6].equals(sudoku[5][8])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
// 6, 0
if(sudoku[6][0].equals(sudoku[6][1]) || sudoku[6][0].equals(sudoku[6][2])
|| sudoku[6][0].equals(sudoku[7][0]) || sudoku[6][0].equals(sudoku[7][1]) || sudoku[6][0].equals(sudoku[7][2])
|| sudoku[6][0].equals(sudoku[8][0]) || sudoku[6][0].equals(sudoku[8][1]) || sudoku[6][0].equals(sudoku[8][2])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
// 6, 3
if(sudoku[6][3].equals(sudoku[6][4]) || sudoku[6][3].equals(sudoku[6][5])
|| sudoku[6][3].equals(sudoku[7][3]) || sudoku[6][3].equals(sudoku[7][4]) || sudoku[6][3].equals(sudoku[7][5])
|| sudoku[6][3].equals(sudoku[8][3]) || sudoku[6][3].equals(sudoku[8][4]) || sudoku[6][3].equals(sudoku[8][5])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
// 6, 6
if(sudoku[6][6].equals(sudoku[6][7]) || sudoku[6][6].equals(sudoku[6][8])
|| sudoku[6][6].equals(sudoku[7][6]) || sudoku[6][6].equals(sudoku[7][7]) || sudoku[6][6].equals(sudoku[7][8])
|| sudoku[6][6].equals(sudoku[8][6]) || sudoku[6][6].equals(sudoku[8][7]) || sudoku[6][6].equals(sudoku[8][8])) {
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
}
if(flag) continue;
// 가로, 세로 검증
for(int i=0; i<9; i++) {
for(int j=0; j<8; j++) {
for(int k=j+1; k<9; k++) {
if(sudoku[i][j].equals(sudoku[i][k])) { // 가로
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
}
for(int k=j+1; k<9; k++) {
if(sudoku[j][i].equals(sudoku[k][i])) { // 세로
System.out.println("#"+ (t+1) + " " +0);
flag = true;
break;
}
}
}
if(flag) break;
}
if(flag) continue;
System.out.println("#"+ (t+1) + " " +1);
}
}
}
다른 사람 풀이
정사각형의 격자를 4중 for문으로 푼게 인상적이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution_D2_1974_스도쿠검증 {
static int[][] map;
static int[] num;
static boolean[] isUsed;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine()); // 테스트케이스 수
for(int t=1; t<=T; t++) {
map = new int[9][9];
for(int i=0; i<9; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<9; j++) {
map[i][j] = Integer.parseInt(st.nextToken()); // 입력받아 표에 저장.
}
}
sb.append("#"+t+" ").append(solving()).append("\n");
}
System.out.println(sb);
}
public static int solving() { // 수평, 수직, 네모에 겹치는 숫자가 없는지 체크
// horizontal 수평체크
for(int i=0; i<9; i++) {
num = new int[10];
isUsed = new boolean[10]; // 배열에 저장된 숫자가 사용되었는지 여부를 저장하는 배열.
for(int j=0; j<9; j++) {
if(isUsed[map[i][j]]) { // 겹치는 숫자가 있다면 0 반환
return 0;
}
isUsed[map[i][j]] = true; // 겹치는 숫자가 없다면 현재 숫자를 사용한 것으로 저장
}
}
// vertival 수직체크
for(int i=0; i<9; i++) {
num = new int[10];
isUsed = new boolean[10];
for(int j=0; j<9; j++) {
if(isUsed[map[j][i]]) {
return 0;
}
isUsed[map[j][i]] = true;
}
}
// squre 네모체크
for(int i=0; i<3; i++) {
for(int j=0; j<3; j++) {
isUsed = new boolean[10];
for(int r=0; r<3; r++) {
for(int c=0; c<3; c++) {
if(isUsed[map[i*3+r][j*3+c]]) { // 인덱스 0, 3, 6 이 첫칸인 행/열을 탐색
return 0;
}
isUsed[map[i*3+r][j*3+c]] = true;
}
}
}
}
return 1; // 겹치는 숫자가 없다면 1 반환
}
}'알고리즘 > SWEA' 카테고리의 다른 글
| [SWEA / 어디에 단어가 들어갈 수 있을까 / JAVA] (0) | 2023.04.27 |
|---|---|
| [SWEA / 초심자의 회문 검사 / JAVA] (0) | 2023.04.25 |
| [SWEA / 달팽이 숫자 / JAVA] (0) | 2023.04.06 |
| [SWEA / 간단한 압축 풀기 / JAVA] (0) | 2023.04.04 |
| [SWEA / 조교의 성적 매기기 / JAVA] (0) | 2023.03.30 |
댓글