스도쿠 검증 C++, Python(SW Expert Academy)

난이도 : D2

문제번호 : 1974

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Psz16AYEDFAUq

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

스도쿠는 숫자퍼즐로, 가로 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부터 시작한다.)

예시

입력	출력
1 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

---

2. 문제풀이

1~9중복되는 값이 없다는것에 착안하여 풀었습니다. 1~9까지 체크를 위한 배열을 만들고 숫자가 들어올때마다 체크하여 중복일시 0을 리턴하게 만들었습니다. 가로세로가 이상이없다면 3x3의 배열을 검사하도록 만들었습니다. 3x3에서도 위와마찬가지로 중복되는 값이 있는지 체크합니다. 모두 통과를 하게되면 1을 출력하게 됩니다.   함수를 이용하여 분리하였고 가로세로를 검사하는 함수와 3x3의 배열을 검사하는 함수를 만들었습니다.

 

---

3. 소스코드

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
//D2 1974 스도쿠 배열 검증
int list[9][9];
//사각형 검사하는 함수
int nextCheck() {
    //제일윗줄부터 오른쪽으로 진행하며 검사
    for (int i = 0; i < 9; i += 3) {
        for (int j = 0; j < 9; j += 3) {
            int sum[10]{ 0 };
            //현재 i와j위치에서 +3개씩 검사
            for (int k = i; k < i + 3; k++) {
                for (int y = j; y < j + 3; y++) {
                    if (sum[list[k][y]])
                        return 0;
                    sum[list[k][y]]++;
                }
            }
        }
    }
    return 1;
}
 
int solution() {
    //스도쿠 데이터를 입력받음
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++)
            cin >> list[i][j];
    }
    //가로세로를 돌면서 중복이 있는지 체크
    for (int i = 0; i < 9; i++) {
        int sum1[10]{ 0 }, sum2[10]{ 0 };
        for (int j = 0; j < 9; j++) {
            if (sum1[list[i][j]] || sum2[list[j][i]])
                return 0;
            sum1[list[i][j]]++;
            sum2[list[j][i]]++;
        }
    }
    //가로세로에 이상이없다면 3칸짜리 삼각형 검사
    return nextCheck();
}
 
int main() {
    int length;
    cin >> length;
    for (int l = 1; l <= length; l++)
        cout << "#" << l << " " << solution() << endl;
    return 0;
}

 

 

sudoku_size = 9
 
def row_column_check(sudoku):
    for i in range(sudoku_size):
        row_validate = [0 for _ in range(sudoku_size)]
        column_validate = [0 for _ in range(sudoku_size)]
        for j in range(sudoku_size):
            row_number = sudoku[i][j] - 1 
            column_number = sudoku[j][i] - 1
            if row_validate[row_number] == 1 or column_validate[column_number] == 1:
                return False
            row_validate[row_number] = 1
            column_validate[column_number] = 1
    return True
 
 
def three_by_three_check(start_y, start_x, sudoku):
    validate = [0 for _ in range(sudoku_size)]
    for i in range(start_y, start_y+3):
        for j in range(start_x, start_x+3):
            number = sudoku[i][j] - 1
            if validate[number] == 1:
                return False
            validate[number] = 1
    return True
 
 
def solution(sudoku):
    if row_column_check(sudoku) == False:
        return 0
    for i in range(0, sudoku_size, 3):
        for j in range(0, sudoku_size, 3):
            if three_by_three_check(i, j, sudoku) == False:
                return 0
    return 1
 
 
for t in range(int(input())):
    sudoku = [list(map(int, input().split())) for _ in range(sudoku_size)]
    answer = solution(sudoku)
 
    print('#{} {}'.format(t+1, answer))