[백준] 2580번 스도쿠 Javascript(NodeJs)

문제링크

https://www.acmicpc.net/problem/2580

알고리즘: 백트래킹

문제 요약

스도쿠라는 9x9 퍼즐판의 빈 칸을 채우는 문제.
빈 칸을 채우는 방식은 다음과 같다.
1.각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 함.

풀이 요약

Well Known 문제라고 한다. 하지만 난 처음 접해봐서 좀 힘들었다.
일단 스도쿠판에 빈칸 좌표를 배열에 다 넣고 백트래킹을 하면 된다. 현재 좌표에 들어갈 수 있는
숫자가 있다면 그 값을 넣고 하위 좌표를 탐색하는데 만약에 좌표에 들어갈 수 있는 숫자가 없다면 다시 상위 좌표로 되돌아가서 들어갈 수 있는 숫자 중 다른 숫자 값을 하나 넣어주고 다시 하위 좌표를 탐색해준다. 이런 방식으로 반복하면서 마지막 좌표에 숫자가 들어간다면 스도쿠판에 빈칸들이 다 채워졌기 때문에 탐색을 종료시키고 스도쿠판을 출력하면 끝이다.

소스코드

const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let board = Array.from(Array(9), () => Array(9));
let blank = [];
let blank_visited = Array.from(Array(9), () => Array(9).fill(false));
for(let i=0; i<inputData.length; i++) {
    let input = inputData[i].trim().split(' ').map(x=>x*1);
    for(let j=0; j<input.length; j++) {
        board[i][j] = input[j];
        if(input[j] === 0) {
            blank.push([j,i]);
        }
    }
}
if(blank.length !==0) {
    DFS(0);
}
let answel = '';
for(let i=0; i<board.length; i++) {
    for(let j=0; j<board[i].length; j++) {
        answel += `${board[i][j]} `
    }
    answel.trim();
    answel += '\n';
}
console.log(answel.trim());

function DFS(index) {
    let [x,y] = blank[index];
    let nums = find_nums(x,y);
    for(let i=0; i<nums.length; i++) {
        board[y][x] = nums[i];
        if(index+1 === blank.length) return; // 다음 탐색이 없다면 리턴.
        let next_ind = index + 1; //다음 탐색 인덱스
        DFS(next_ind); //하위 탐색
        let [nx, ny] = blank[next_ind]; //하위 탐색에 좌표값.
        if(board[ny][nx] !== 0) return; // 하위 탐색에서 성공했다면 리턴.
        board[y][x] = 0; //그게 아니라면 0값 넣어줌.
    }
}

function find_nums(x,y) {
    let num_arr = [];
    let num_check = new Array(10).fill(false);
    for(let i=0; i<9; i++) {
        if(board[y][i] !== 0) {
            num_check[board[y][i]] = true;
        }
        if(board[i][x] !== 0) {
            num_check[board[i][x]] = true;
        }
    }
    let sx = parseInt(x/3) * 3;
    let sy = parseInt(y/3) * 3;
    for(let i=sy; i<sy+3; i++) {
        for(let j=sx; j<sx+3; j++) {
            if(board[i][j] !== 0) {
                num_check[board[i][j]] = true;
            }
        }
    }
    for(let i=1; i<num_check.length; i++) {
        if(!num_check[i]) {
            num_arr.push(i);
        }
    }
    return num_arr;
}