[SWEA 1974][D2][JAVA] 스도쿠 검증

[문제]

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Psz16AYEDFAUq&categoryId=AV5Psz16AYEDFAUq&categoryType=CODE

SW Expert Academy

[풀이방법]

 

가로 / 세로 / 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 이차원 배열을 초기화 해주었습니다. 

 

설명과 코드를 보면서 차근 차근 이해해주세요

 

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++) {
            sf.append("#" + (k+1) + " ");
 
            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) {
                sf.append(ans + "\n");
                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) {
                sf.append(ans + "\n");
                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;
            }
 
            sf.append(ans + "\n");
        }
        System.out.println(sf.toString());
    }
}