백준 2239: 스도쿠 - javascript(백트래킹)

문제 출처 

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

 

정답 풀이 

다른 분의 풀이를 참고했는데, 

오 어떻게 이런 생각을? ..? 기가 막히다 

 

1. 먼저 주어진 스도쿠, 즉, board에서 0인 좌표를 zero 배열에 넣자. 

2. 해당 zero 를 dfs 로 탐색을 한다. 

3. 모든 zero 좌표를 다 돌았을 때의 board를 출력한다. 

4. dfs 함수는 zero idx를 하나씩 올린다. 

5. - 조건은 check 함수에 해당 좌표와 숫자를 넣었을 때 true 값이 출력되야 한다. 

6. check 함수는 해당 좌표의 행과 열을 확인해서 같은 숫자가 있으면 false, 해당 작은 3*3 좌표에서 같은 숫자가 있으면 false 

정답 코드 

const board = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(el => el.split('').map(v => +v)); 

const zero = []; 
for(let i=0; i<9; i++){
    for(let j=0; j<9; j++){
        if(board[i][j] === 0) zero.push([i,j])
    }
}

function dfs(now){
    if(now === zero.length){
        console.log(board.map(v => v.join('')).join('\n'))
        process.exit()
    }
    const [x,y] = zero[now]; 
    for(let i=1; i<10; i++){
        if(check(x,y,i)){
            board[x][y] = i; 
            dfs(now+1); 
            board[x][y] = 0
        }
    }
}

dfs(0)

function check(x,y,n){
    for(let j=0; j<9; j++){
        if(board[x][j] === n) return false; 
    }
    for(let i=0; i<9; i++){
        if(board[i][y] === n) return false; 
    }
    
    const X = Math.floor(x/3)*3
    const Y = Math.floor(y/3)*3
    
    for(let i=X; i<X+3; i++){
        for(let j=Y; j<Y+3; j++){
            if(board[i][j] === n) return false; 
        }
    }
    return true; 
}


//가로줄부터 0이면 배열에 넣기 
//dfs 해당 zero 배열 길이가 되면 멈추기