ALGORITHM

[SWEA] 1974. 스도쿠 검증 (java)

charBS 2024. 1. 11. 00:08

시간 : 10개 테스트케이스를 합쳐서 C의 경우 30초 / C++의 경우 30초 / Java의 경우 30초 / Python의 경우 30초

메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내


문제

스도쿠는 숫자퍼즐로, 가로 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
...


내 풀이

import java.util.Scanner;
import java.io.FileInputStream;
  
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int[][] sudoku = new int[9][9];
            for (int i=0; i<9; i++) {    // 스토쿠 입력
                for (int j=0; j<9; j++) {
                    sudoku[i][j] = sc.nextInt();
                }
            }
              
            // 스토쿠 검사
            int result = 1;
            // 가로
            for (int i=0; i<9; i++) {
                int[] row_table = new int[10];
                int[] col_table = new int[10];
                for (int j=0; j<9; j++) {    
                    if (row_table[sudoku[i][j]] == 1 || col_table[sudoku[j][i]] == 1) { // 가로검사, 세로검사
                        result = 0;
                        break;
                    } else {
                        row_table[sudoku[i][j]]=1;
                        col_table[sudoku[j][i]]=1;
                    }
                }
                if ( result==0) break;
            }
              
            // 3x3 검사
            for (int d=0; d<3; d++) {
                if (result==0) break;
                int[] table = new int[10];
                for (int x=0; x<3; x++) {
                    for (int y=0; y<3; y++) {
                        if (table[sudoku[d*3+x][d*3+y]]==1) {
                            result=0;
                            break;
                        } else {
                            table[sudoku[d*3+x][d*3+y]]=1;
                        }
                    }
                }
            }           
              
            System.out.printf("#%d %d\n", test_case, result);
        }
    }
}

 

3x3의 칸을 처리하는데 애를 먹었지만 뭐 이렇게 하면 되겠지? 하고 돌려봤는데 바로 성공해서 "이게 왜 되지?" 했다.