문제 : sudoku
일부 칸이 비어있는 상태인 스도쿠 보드를 입력받아 스도쿠 퍼즐이 완성된 보드를 리턴해야 합니다.
let board = [
[0, 3, 0, 2, 6, 0, 7, 0, 1],
[6, 8, 0, 0, 7, 0, 0, 9, 0],
[1, 9, 0, 0, 0, 4, 5, 0, 0],
[8, 2, 0, 1, 0, 0, 0, 4, 0],
[0, 0, 4, 6, 0, 2, 9, 0, 0],
[0, 5, 0, 0, 0, 3, 0, 2, 8],
[0, 0, 9, 3, 0, 0, 0, 7, 4],
[0, 4, 0, 0, 5, 0, 0, 3, 6],
[7, 0, 3, 0, 1, 8, 0, 0, 0],
];
let output = sudoku(board);
console.log(output); // -->
/*
[
[4, 3, 5, 2, 6, 9, 7, 8, 1],
[6, 8, 2, 5, 7, 1, 4, 9, 3],
[1, 9, 7, 8, 3, 4, 5, 6, 2],
[8, 2, 6, 1, 9, 5, 3, 4, 7],
[3, 7, 4, 6, 8, 2, 9, 1, 5],
[9, 5, 1, 7, 4, 3, 6, 2, 8],
[5, 1, 9, 3, 2, 6, 8, 7, 4],
[2, 4, 8, 9, 5, 7, 1, 3, 6],
[7, 6, 3, 4, 1, 8, 2, 5, 9],
];
*/문제의 접근
너무 많은 산을 거쳐가야 하지만 하나하나 차근차근 생각해보기로 했다.우선은 각 1~9가 한번씩만 들어갈 수 있는 구역들을 배열로 정의해 봤다.
const sudoku = function (board) {
// TODO: 여기에 코드를 작성합니다.
const numbers = [1,2,3,4,5,6,7,8,9]
let area = [[],[],[],[],[],[],[],[],[]]
let calum = [[],[],[],[],[],[],[],[],[]]
let row = [[],[],[],[],[],[],[],[],[]]
let index = 0;
const getArea = (startI, startJ, index) => { //구역에 값을 넣어주는 함수
for(let i = startI; i < startI + 3; i++){
for(let j = startJ; j < startJ + 3; j++){
if(board[i][j] !== 0){
area[index].push(board[i][j])
}
}
}
}
for(let i = 0; i < 9; i+=3){ //구역 값 정의
for(let j = 0; j < 9; j+=3){
getArea(i, j, index);
index++;
}
}
for(let i = 0; i < 9; i++){ //열 값 정의
for(let j = 0; j < 9; j++){
if(board[i][j] !== 0){
calum[j].push(board[i][j])
row[i].push(board[i][j])
}
}
}
};이제는 탐욕법이다. 이걸 모든 경우의 수를 생각한다면 바둑경기의 수랑 비등한 경우의 수가 도출 될 것이다. 그렇다면 이 문제는 어떻게 풀어야 할까...?
당장 생각나는 방법은 탐욕법이다. 모든 경우의 수를 선택 할 수 없으니 당연히 최적의 선택을 해가야 한다. 그렇다면 다시 탐욕법을 재귀 함수로 만들어 줘야 한다...
만들다가 다시 생각해보니 탐욕법이 아니라 DFS를 사용해야 할 것 같다. 해보고 안되면 다른 숫자를 넣어보면서 검사해야 할 것 같다.
그러기 위해서는 일단 0의 자리에 들어갈 수 있는 값을 검사해주는 함수를 만들어야 겠다.
const isValid = (indexi, indexj, areaNum, num){ //그 값이 들어갈 수 있는지 없는지 검사
if(!row[indexi].inclued(num) && !calum[indexj].inclued(num) && !area[areaNum].inclued(num)){
return true;
}
return false;
}위 함수는 어떤 값을 넣었을 때 그 값이 어떤 구역에도 포함되어있지 않으면 ture를 아니면 false를 리턴하게 되어 있다. 이제 이걸 이용해서 배열을 순회하면서 넣을 수 있는 값을 넣어줄 것이다.
이 문제는 시간 초과로 포기....🥲
정말 혼자 힘으로 풀어보고 싶었지만 이 문제에만 매달릴 시간이 없는 관계로 레퍼런스 코드를 보고 이해하기로 했다...
정답
const sudoku = function (board) {
const N = board.length; // N === 9
const boxes = [
[0, 0, 0, 1, 1, 1, 2, 2, 2],
[0, 0, 0, 1, 1, 1, 2, 2, 2],
[0, 0, 0, 1, 1, 1, 2, 2, 2],
[3, 3, 3, 4, 4, 4, 5, 5, 5],
[3, 3, 3, 4, 4, 4, 5, 5, 5],
[3, 3, 3, 4, 4, 4, 5, 5, 5],
[6, 6, 6, 7, 7, 7, 8, 8, 8],
[6, 6, 6, 7, 7, 7, 8, 8, 8],
[6, 6, 6, 7, 7, 7, 8, 8, 8],
];
const getBoxNum = (row, col) => boxes[row][col];
const blanks = [];
const rowUsed = [];
const colUsed = [];
const boxUsed = [];
for (let row = 0; row < N; row++) {
rowUsed.push(Array(N + 1).fill(false));
colUsed.push(Array(N + 1).fill(false));
boxUsed.push(Array(N + 1).fill(false));
}
for (let row = 0; row < N; row++) {
for (let col = 0; col < N; col++) {
if (board[row][col] === 0) {
blanks.push([row, col]);
} else {
const num = board[row][col];
const box = getBoxNum(row, col);
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[box][num] = true;
}
}
}
const isValid = (row, col, num) => {
const box = getBoxNum(row, col);
return (
rowUsed[row][num] === false &&
colUsed[col][num] === false &&
boxUsed[box][num] === false
);
};
const toggleNum = (row, col, num) => {
const box = getBoxNum(row, col);
board[row][col] = num;
rowUsed[row][num] = !rowUsed[row][num];
colUsed[col][num] = !colUsed[col][num];
boxUsed[box][num] = !boxUsed[box][num];
};
const aux = (idx, blanks, board) => {
if (idx === blanks.length) {
return true;
}
const [row, col] = blanks[idx];
for (let num = 1; num <= 9; num++) {
if (isValid(row, col, num) === true) {
toggleNum(row, col, num);
if (aux(idx + 1, blanks, board) === true) {
return true;
}
toggleNum(row, col, num);
}
}
return false;
};
aux(0, blanks, board);
return board;
};문제를 통해 생각해 볼 것
솔직히 시간이 더 있었다면 충분히 풀었을 거라는 생각이 든다. 하지만 지금 여건이 여건이니 만큼 알고리즘 문제만 붙잡고 있을 시간이 없어서 안타까울 뿐이다...
문제의 접근 방식은 정답과 크게 벗어나지 않았다고 생각된다. 하지만 코드를 짜는 부분에서 너무 장황해진 내 코드가 보인다... 조금 더 트레이닝을 통해서 생각한걸 코드로 잘 구현하는 연습을 많이 해야 할 것 같다.
그래도 문제 접근 방식은 맞춘 것 같아 기쁘다.😃
