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

SW Expert Academy

우리가 흔히 아는 스도쿠를 활용한 문제이다.

9X9의 배열을 입력받아서, 해당 배열이 스도쿠 퍼즐에 부합하는지를 검증하는 문제이다.

 

풀이

import java.util.Scanner;

public class S_1974 {
    static int[][] sudoku;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // test case

        for (int i = 0; i < t; i++) {
            // 스도쿠 배열 입력받기
            sudoku = new int[9][9];
            for (int j = 0; j < 9; j++) {
                for (int k = 0; k < 9; k++) {
                    sudoku[j][k] = sc.nextInt();
                }
            }
            System.out.println("#" + (i+1) + " " + solve());
        }
    }
    static int solve() {
        // 가로 배열마다 중복 확인하기
        for (int j = 0; j < 9; j++) {
            int[] test = new int[10];
            for (int k = 0; k < 9; k++) {
                test[sudoku[j][k]]++;
            }
            for (int i = 1; i <= 9; i++) {
                if (test[i] != 1) {
                    return 0;
                }
            }
        }

        // 세로 배열마다 중복 확인하기
        for (int i = 0; i < 9; i++) {
            int[] test = new int[10];
            for (int j = 0; j < 9; j++) {
                test[sudoku[j][i]]++;
            }
            for (int j = 1; j <= 9; j++) {
                if (test[j] != 1) {
                    return 0;
                }
            }
        }

        // 구간마다 중복 확인하기
        int one = 0;
        int two = 0;
        for (int i = 0; i < 9; i++) {
            int[] test = new int[10];
            for (int j = one; j < one+3; j++) {
                for (int k = two; k < two+3; k++) {
                    test[sudoku[j][k]]++;
                }
            }
            if (i < 2) {
                two += 3;
            } else if (i == 2) {
                two = 0;
            } else if (i < 5) {
                one = 3;
                two += 3;
            } else if (i == 5) {
                two = 0;
            } else {
                one = 6;
                two += 3;
            }
            for (int j = 1; j <= 9; j++) {
                if (test[j] != 1) {
                    return 0;
                }
            }
        }
        return 1;
    }
}

해당 배열이 가로, 세로, 3X3 구간이 모두 중복 없는 숫자를 만족하는 스도쿠 퍼즐인지 검증하는 solve() 함수를 구현하였다. 스도쿠의 조건을 만족하면 1, 조건을 만족하지 않으면 0을 return 한다.

// 가로 배열마다 중복 확인하기
for (int j = 0; j < 9; j++) {
    int[] test = new int[10];
    for (int k = 0; k < 9; k++) {
      test[sudoku[j][k]]++;
    }
    for (int i = 1; i <= 9; i++) {
      if (test[i] != 1) {
           return 0;
      }
   }
}

먼저 가로 배열의 중복 여부를 검사했다.

1부터 9까지의 숫자가 중복 없이 들어있는지 검사하기 위한 test 배열을 새로 만들었다. 만일 test 배열에 모두 1이 들어있지 않다면 중복된 수가 있다는 의미이기 때문에 바로 0을 return 한다.

// 세로 배열마다 중복 확인하기
for (int i = 0; i < 9; i++) {
    int[] test = new int[10];
    for (int j = 0; j < 9; j++) {
       test[sudoku[j][i]]++;
   }
   for (int j = 1; j <= 9; j++) {
       if (test[j] != 1) {
            return 0;
        }
    }
}

위와 동일한 방식으로 세로 배열의 중복 여부를 검사해준다.

// 구간마다 중복 확인하기
int one = 0;
int two = 0;
for (int i = 0; i < 9; i++) {
    int[] test = new int[10];
    for (int j = one; j < one+3; j++) {
      for (int k = two; k < two+3; k++) {
          test[sudoku[j][k]]++;
      }
    }
    if (i < 2) {
       two += 3;
    } else if (i == 2) {
        two = 0;
    } else if (i < 5) {
        one = 3;
        two += 3;
    } else if (i == 5) {
        two = 0;
    } else {
        one = 6;
        two += 3;
    }
    for (int j = 1; j <= 9; j++) {
        if (test[j] != 1) {
            return 0;
        }
    }
}

스도쿠 퍼즐에는 중복되지 않은 총 9개의 정사각형 구간이 있다.

해당 9개 구간 또한 중복된 수가 있는지 검증해주었다.

 

처음에는 1부터 9까지의 합인 45로 검증을 할까 생각했는데, 모든 숫자가 5일 때와 같은 예외 케이스가 있어서 반려하였다. 해당 문제의 댓글을 보아하니 팩토리얼 또는 곱셈으로 검증하는 아이디어도 있었다. 

스도쿠의 개념을 대부분 다 알고 있을 것이기 때문에 그것을 염두하고 구현하면 어렵지는 않을 것 같다.