📜 문제
- 부분적으로 채워진 9x9 크기의 Sudoku Board가 주어진다.
- 채워진 cell 들이 규칙에 부합하면
true, 그렇지 않으면false를 반환한다.
규칙
1. 각 행은 1~9 숫자들을 한 번만 쓸 수 있다.
2. 각 열은 1~9 숫자들을 한 번만 쓸 수 있다.
3. 3x3 크기의 내부 9개 상자들은 각각 1~9 숫자들을 한 번만 쓸 수 있다.
기존에 알고 있던 스도쿠 규칙과 동일해서 어떻게 해야 좀 더 깔끔하게 짤 수 있을지 고민했다.
접근 1
- Sudoku Box 전체를 순회하면서 각 행, 열별로 규칙을 만족하는지 확인하기.
내부 상자의 경우, 3x3이 한 세트이므로 row와 col이 0, 3, 6일 때만 확인.
단순하게 풀 수 있는 방법이지만, 굳이 스도쿠 전체를 순회하지 않아도 풀 수 있을 거 같다.
접근 2
- 박스는 정사각형이니까, 행과 열의 개수는 동일하다.
행 별로 colum 값을 1~9까지 돌고, 마찬가지로 열 별로 row 값을 1~9까지 돌면
좀 더 깔끔할 것 같다.
예시
idx =0일 때 (1행, 1열 검사)
1행 검사:5,3,7(row:1, col=1~9)
1열 검사:5, 6, 8, 4, 7(col=1, row:1~9)
<Integer, Boolean> Map타입의 map을 선언해서, 매 행, 열을 돌면서 저장해준다.
Map의 key 값이 이미 존재하는 경우, 스도쿠 규칙을 어겼다고 판단하고 false를 반환하면 될 것 같다.
✍ 부분 코드 설명
main 함수
class Solution{
static HashMap<Character, Boolean> valid;
public boolean isValidSudoku(char[][] board) {
for(int r=0,c=0;r<board.length;r++,c++){
if(!Rowcheck(board,r)){
return false;
}
if(!Colcheck(board,c)){
return false;
}
}
// check sub-Box
for(int r=0;r<board.length;r+=3){
for(int c=0;c<board[0].length;c+=3){
if(!Boxcheck(board, r,c)) return false;
}
}
return true;
}
...
}-
각 행, 열이 포함하고 있는 숫자를 저장할 Map 변수 valid를 선언한다.
-
먼저, 행과 열을 검사한다.
Sudoku Board 크기 만큼 행을 검사하는RowCheck, 열을 검사하는ColCheck함수를 호출한다. -
각 행/열이 스도쿠 규칙을 만족한다면, 내부 상자가 규칙을 지키는지 확인한다.
RowCheck / ColCheck
...
public static boolean Rowcheck(char[][] board, int row){
valid = new HashMap<>();
for(char c: board[row]){
if(c =='.') continue;
if(HandleValid(c, valid)){
return false;
}
}
return true;
}
public static boolean Colcheck(char[][] board, int col){
valid = new HashMap<>();
for(int r=0;r<board.length;r++){
if(board[r][col]=='.') continue;
if(HandleValid(board[r][col], valid))
return false;
}
}
return true;
}
...-
Rowchek 함수
비어있는 cell인 경우 그냥 지나치기. 비어있지 않으면 HandleValid 함수 호출
반환값이true인 경우 규칙을 어겼으므로false를 반환한다. -
ColCheck 함수
Row 함수와 동일하게 작동
HandleValid 함수
...
public static boolean HandleValid(char c, HashMap<Character, Boolean> valid){
if(!valid.getOrDefault(c,false)){
valid.put(c,true);
return false;
}
return true;
}
...매개변수로 들어온 c 값이 map에 존재하는지 확인한다.
존재하지 않는 경우, valid.put(c, true) 코드가 호출하여 c를 저장하고, false를 반환한다.
이미 map에 c가 존재하는 경우 true를 반환한다.
즉, 이미 c와 동일한 값이 map에 존재하는 경우, 스도쿠 규칙을 어긴 것이다.
BoxCheck 함수
main 함수{
...
for(int r=0;r<board.length;r+=3){
for(int c=0;c<board[0].length;c+=3){
if(!Boxcheck(board, r,c)) return false;
}
}
}
public static boolean Boxcheck(char[][] board, int row, int col){
valid= new HashMap<>();
for(int r=row;r<row+3;r++){
for(int c=col;c<col+3;c++){
if(board[r][c]=='.') continue;
if(HandleValid(board[r][c],valid)){
return false;
}
}
}
return true;
}- 모든 행, 열이 규착을 만족한 경우, 호출하는 BoxCheck 코드이다.
내부 상자의 좌상단 좌표는 아래 그림과 같다.
- main 함수에서 내부 상자 별로 BoxCheck 함수를 호출한다.
호출되 내부 상자는 내부를 순회하며 HandleValid 함수를 호출한다.
HandleValid 함수는 RowCheck, ColCheck과 같은 방식으로 작동한다.
🍳 전체 소스 코드
class Solution {
static HashMap<Character, Boolean> valid;
public static boolean HandleValid(char c, HashMap<Character, Boolean> valid){
if(!valid.getOrDefault(c,false)){
valid.put(c,true);
return false;
}
return true;
}
public static boolean Rowcheck(char[][] board, int row){
valid = new HashMap<>();
for(char c: board[row]){
if(c =='.') continue;
if(HandleValid(c, valid)){
return false;
}
}
return true;
}
public static boolean Colcheck(char[][] board, int col){
valid = new HashMap<>();
for(int r=0;r<board.length;r++){
if(board[r][col]=='.') continue;
if(HandleValid(board[r][col], valid)){
return false;
}
}
return true;
}
public static boolean Boxcheck(char[][] board, int row, int col){
valid= new HashMap<>();
for(int r=row;r<row+3;r++){
for(int c=col;c<col+3;c++){
if(board[r][c]=='.') continue;
if(HandleValid(board[r][c],valid)){
return false;
}
}
}
return true;
}
public boolean isValidSudoku(char[][] board) {
for(int r=0,c=0;r<board.length;r++,c++){
if(!Rowcheck(board,r)){
return false;
}
if(!Colcheck(board,c)){
return false;
}
}
// check sub-Box
for(int r=0;r<board.length;r+=3){
for(int c=0;c<board[0].length;c+=3){
if(!Boxcheck(board, r,c)) return false;
}
}
return true;
}
}✨ 결과
기능별로 함수를 분리하려고 연습하는 중이다.
HandleValid 함수의 함수명이 아숩고,, 반환값 처리 방식도 아쉽긴하다.
isNotValid 로 함수명을 변경하고 true, false 처리 방식을 변경하면 가독성이 향상될 것 같다.
