[D2] SWEA - 1974. 스도쿠 검증 : Java

SW Expert Academy

 

 

 

문제

스도쿠는 숫자퍼즐로, 가로 9칸 세로 9칸으로 이루어져 있는 표에 1 부터 9 까지의 숫자를 채워넣는 퍼즐이다.

같은 줄에 1 에서 9 까지의 숫자를 한번씩만 넣고, 3 x 3 크기의 작은 격자 또한, 1 에서 9 까지의 숫자가 겹치지 않아야 한다.

입력으로 9 X 9 크기의 스도쿠 퍼즐의 숫자들이 주어졌을 때, 위와 같이 겹치는 숫자가 없을 경우, 1을 정답으로 출력하고 그렇지 않을 경우 0 을 출력한다.

 

 

[제약 사항]
1. 퍼즐은 모두 숫자로 채워진 상태로 주어진다.
2. 입력으로 주어지는 퍼즐의 모든 숫자는 1 이상 9 이하의 정수이다.

[입력]
입력은 첫 줄에 총 테스트 케이스의 개수 T가 온다.
다음 줄부터 각 테스트 케이스가 주어진다.
테스트 케이스는 9 x 9 크기의 퍼즐의 데이터이다.

[출력]
테스트 케이스 t에 대한 결과는 “#t”을 찍고, 한 칸 띄고, 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

입력

10
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 1
...

 

 

 

풀이1 - 실패

    private static int checkMap(int[][] map, int size) {        
        // 가로줄 확인
        for (int i = 0; i < size; i++) {
            int[] check = new int[size];
            for (int j = 0; j < size; j++) {
                check[map[i][j] - 1] = 1;
            }
            
            for (int j = 0; j < size; j++) {
                if (check[j] != 1) {
                    return 0;
                }
            }
        }
        
        // 세로줄 확인
        for (int j = 0; j < size; j++) {
            int[] check = new int[size];
            for (int i = 0; i < size; i++) {
                check[map[i][j] - 1] = 1;
            }
            
            for (int i = 0; i < size; i++) {
                if (check[j] != 1) {
                    return 0;
                }
            }
        }
        
        // 3X3 확인
        for (int i = 0; i < size; i += 3) {
            int[] check = new int[size];
            for (int j = 0; j < size; j += 3) {
                for (int k = 0; k < 3; k++) {
                    check[map[i + k][j + k] - 1] = 1;
                    check[map[i][j + k] - 1] = 1;
                    check[map[i + k][j] - 1] = 1;
                }
            }
            for (int j = 0; j < size; j++) {
                if (check[j] != 1) {
                    return 0;
                }
            }
        }
        
        return 1;
    }

• 3X3을 확인하는 로직이 잘못된 것으로 추정됨

 

 

풀이2

참고

[java] 스도쿠 검증 (SWEA, 1974) - LunaLunaఇ

    private static int checkMap(int[][] map, int size) {        
        // 가로 & 세로 확인
        for (int i = 0; i < size; i++) {
            int rowSum = 0;
            int colSum = 0;
            
            for (int j = 0; j < size; j++) {
                rowSum += map[i][j];
                colSum += map[j][i];
            }
            
            if (rowSum != 45 || colSum != 45) {
                return 0;
            }
        }
        
        // 3X3 확인
        for (int i = 0; i < size; i += 3) {
            for (int j = 0; j < size; j += 3) {
                int sum = 0;
                
                for (int k = 0; k < 3; k++) {
                    for (int p = 0; p < 3; p++) {
                        sum += map[i + k][j + p];
                    }
                }
                
                if (sum != 45) {
                    return 0;
                }
            }
        }
        
        return 1;
    }

• 가로와 세로를 한 번에 확인하여 효율적
• int 배열로 체크하는 것이 아닌, 전체 합인 45와 같은지 확인
  • 개인적으로 이 방법이 확실한 방법은 아니라는 생각이 들어 사용하지 않았는데, 찾아보니 대부분 이 방식으로 풀이함
• 단점 : 4중 for문 사용으로 인한 가독성 저하

 

 

풀이3 - chatgpt

    private static boolean isValidSudoku(int[][] map, int size) {        
        // 가로 & 세로 & 3X3 확인
        for (int i = 0; i < size; i++) {
            Set<Integer> rowSet = new HashSet<>();
            Set<Integer> colSet = new HashSet<>();
            Set<Integer> boxSet = new HashSet<>();
            
            for (int j = 0; j < size; j++) {
                if (!rowSet.add(map[i][j])) return false;
                    
                if (!colSet.add(map[j][i])) return false;
                
                int rowIndex = 3 * (i / 3) + j / 3;
                int colIndex = 3 * (i % 3) + j % 3;
                if (!boxSet.add(map[rowIndex][colIndex])) return false;
            }
        }
        
        return true;
    }

• 가로, 세로, 3X3을 한 번에 확인
• HashSet 사용
• rowIndex와 colIndex를 구하는 식이 핵심

0	0	3 * (0 / 3) + 0 / 3 = 0	3 * (0 % 3) + 0 % 3 = 0	(0, 0)
0	1	3 * (0 / 3) + 1 / 3 = 0	3 * (0 % 3) + 1 % 3 = 1	(0, 1)
0	2	3 * (0 / 3) + 2 / 3 = 0	3 * (0 % 3) + 2 % 3 = 2	(0, 2)
0	3	3 * (0 / 3) + 3 / 3 = 1	3 * (0 % 3) + 3 % 3 = 0	(1, 0)
0	4	3 * (0 / 3) + 4 / 3 = 1	3 * (0 % 3) + 4 % 3 = 1	(1, 1)
0	5	3 * (0 / 3) + 5 / 3 = 1	3 * (0 % 3) + 5 % 3 = 2	(1, 2)
0	6	3 * (0 / 3) + 6 / 3 = 2	3 * (0 % 3) + 6 % 3 = 0	(2, 0)
0	7	3 * (0 / 3) + 7 / 3 = 2	3 * (0 % 3) + 7 % 3 = 1	(2, 1)
0	8	3 * (0 / 3) + 8 / 3 = 2	3 * (0 % 3) + 8 % 3 = 2	(2, 2)

• 4중 for문을 사용하지 않아도 되며, 중복 확인을 한 번에 할 수 있음
• 단점 : 메모리 사용량 증가 (9X9 스도쿠는 차지하는 양이 미미하기에 괜찮다고 생각됨)