9×9 크기의 행렬 형태로 주어진 스도쿠 보드가 있다고 가정해 보겠습니다. 이때 우리의 과제는 해당 스도쿠 패턴이 유효한지 아닌지를 판별하는 것입니다.
일반적인 스도쿠 보드는 다음과 같은 모양을 하고 있습니다.
스도쿠의 기본 규칙
모든 행에는 1~9 범위의 숫자가 포함되어야 합니다.
모든 열에도 1~9 범위의 숫자가 포함되어야 합니다.
각 3×3 블록 안에는 서로 중복되지 않는 숫자만 존재해야 합니다.
하나의 행 안에서 같은 숫자가 반복될 수 없습니다.
하나의 열 안에서도 같은 숫자가 반복될 수 없습니다.
예시
입력-1 −
sudoku[]=
[["3","5",".",".","2",".",".",".","."]
,["7",".",".","1","6","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","5",".","4",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
출력 − True
설명 − 스도쿠 행렬 안의 모든 숫자가 유효한 스도쿠 패턴을 따르고 있으므로, 출력 결과는 True입니다.
문제 해결 접근 방식
먼저 주어진 스도쿠 보드의 각 열(column)에 중복되지 않은 숫자들이 들어 있는지 확인합니다. 이어서 행(row)을 검사하고, 마지막으로 각 3×3 블록 안의 숫자들이 모두 고유한지 살펴봅니다. 검사 과정에서 어느 부분이라도 중복된 숫자가 발견되면 즉시 false를 반환하고, 모든 검사를 통과하면 true를 반환합니다.
구체적인 구현 단계는 다음과 같습니다.
스도쿠 보드를 2차원 배열(2-D array)로 입력받습니다.
행에 포함된 요소들이 고유한지 검사하는 불리언(Boolean) 함수를 작성합니다.
열에 포함된 요소들이 고유한지 검사하는 불리언 함수를 작성합니다.
3×3 블록에 포함된 요소들이 고유한지 검사하는 불리언 함수를 작성합니다.
C++ 구현 코드
#include<bits/stdc++.h>
using namespace std;
bool validSudoku(vector<vector<char>>& sudoku) {
int row = 0, col = 0, i = 0, block = 0;
int count[9];
for (row = 0; row < 9; ++row){
memset(count, 0, 9 * sizeof(int));
for (col = 0; col < 9; ++col){
if (sudoku[row][col] != '.')
++count[sudoku[row][col]-'1'];
}
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
for (col = 0; col < 9; ++col){
memset(count, 0, 9 * sizeof(int));
for (row = 0; row < 9; ++row){
if (sudoku[row][col] != '.')
++count[sudoku[row][col]-'1'];
}
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
int block_row = 0, block_col = 0;
for (block = 0; block < 9; ++block){
block_row = (block / 3) * 3, block_col = (block % 3) * 3;
memset(count, 0, 9 * sizeof(int));
for (row = block_row; row < (block_row + 3); ++row)
for (col = block_col; col < (block_col + 3); ++col)
if (sudoku[row][col] != '.')
++count[sudoku[row][col] - '1'];
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
return true;
}
int main(){
vector<vector<char> > sudoku= {
{'5','3','.','.','7','.','.','.','.'},
{'6','.','.','1','9','5','.','.','.'},
{'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'},
{'4','.','.','8','.','3','.','.','1'},
{'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'},
{'.','.','.','4','1','9','.','.','5'},
{'.','.','.','.','8','.','.','7','9'}
};
bool ans= validSudoku(sudoku);
if(ans){
cout<<"True"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
실행 결과
True