Node.js) 백준 2580번 : 스도쿠

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

2580번: 스도쿠

 

2239번 스도쿠 (똑같은 문제)

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

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 i = 0; i < 9; i++) {
		if (board[x][i] == 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;
}

 

 

 

 

 

 

 

 

// 이거는 옛날에 풀었던 풀이;; 

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


//정답 보여주기
function showAnswer(x){
    let answer = x.map(v=>v.join(' ')).join('\n')
    console.log(answer)
}


// 비어 있는 부분 찾기
const zero=[];
for(let i =0; i<9; i++){
    for(let j = 0; j<9; j++){
        if(input[i][j]==0){
            zero.push([j,i])
        }
    }
}

//강제종료 어떻게 해야할지 모르겠음..
//그래서 일단 전역변수 하나 만들음
let exit =false;


dfs(0,input)


//dfs
function dfs(cnt,sudoku){
    if(cnt==zero.length){
        showAnswer(sudoku);
        exit=true;
        return;
    }
    if(!exit){ 
        const [x,y] = zero[cnt];
        for(let i = 1; i<10; i++){
            if(check(x,y,i,sudoku)){
                sudoku[y][x] = i;
                dfs(cnt+1,sudoku);
                sudoku[y][x]=0;
            }
        }
       }
       return;
}




//백트래킹 체크
function check(x,y,n,board){

    //x: column, 가로방향 좌표
    //y: row, 세로방향 좌표
    //n: 현재 확인해야하는 값
    //board: 스도쿠 판.


    for(let i= 0; i<9; i++){
        if(board[i][x]==n) return false;
    }
    for(let i = 0; i<9; i++){
        if(board[y][i]==n) return false;
    }

    const X = Math.floor(x/3)*3;
    const Y = Math.floor(y/3)*3;

    for(let i = Y; i<Y+3; i++){
        for( let j  = X; j<X+3; j++){
            if(board[i][j]==n) return false; 
        }
    }
    return true;
}