[Algorithm] 백준 2580 스도쿠 Node.js

스도쿠는 18세기 스위스의 수학자 레온하르트 오일러가 창안한 라틴방진(Latin Square)를 기초로 합니다. 미국의 건축가 하워드 간즈(Howard Garns)가 넘버플레이스라는 이름으로 1979년 소개했습니다. 대중화 된 계기는 1984년 일본 니코리사 <퍼즐통신 니코리>에서 스도쿠라는 이름을 붙여 판매하면서 알려지기 시작했습니다. 

 

 

스도쿠를 푸는 방법은 간단합니다. 3가지 규칙에 부합하는 숫자를 찾아 빈칸에 입력하면 됩니다.

1. 가로줄 중 1~9가 중복없이 들어가야 합니다.
2. 세로줄 중 1~9가 중복없이 들어가야 합니다.
3. 3x3 칸 중 1~9가 중복없이 들어가야 합니다.

 

백준 2580 스도쿠 문제

 

문제

 

스도쿠 문제를 푼 최종 모습을 출력하세요

 

입/출력

 

입력

아홉줄에 걸쳐 한줄에 9개씩 숫자가 입력됩니다. 숫자가 채워져야 하는 칸에는 '0'이 채워져 있습니다.

출력

0으로 채워진 빈칸을 모두 채운 스도쿠를 한칸씩 띄운 모습으로 출력합니다.

 

입출력 예제

// 입력
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

//출력
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

 

풀이

 

 

스도쿠를 풀기 위한 방법은 가로, 세로, 박스 내 중복값이 없어야 합니다. 먼저 가로, 세로, 박스의 중복값을 담을 Boolean 배열을 선언합니다. 3x3 내 숫자를 뽑아내기 위해서는 9x9 로 이뤄진 배열에 0~8까지의 값을 입력합니다. box내 값을 출력할 getBoxNum 함수를 선언합니다.

 

 

const N = board.length;
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 blanks = [];
const rowUsed = [];
const colUsed = [];
const boxUsed = [];
const getBoxNum = (row, col) => boxes[row][col];

 

주어진 board의 길이만큼 순회하면서 가로, 세로, 박스의 중복값을 담은 Boolean 배열을 false로 초기화 합니다.

for(let i=0; i<N; i++){
    rowUsed.push(Array(N+1).fill(false));
    colUsed.push(Array(N+1).fill(false));
    boxUsed.push(Array(N+1).fill(false));
}

 

입력값으로 주어진 board 2차원 배열을 순회하면서 빈칸을 탐색합니다. 0인 경우 빈칸이므로 blanks 배열에 좌표값을 추가하고, 0이 아닌 경우 가로, 세로, 박스 배열을 true를 입력합니다.

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 box = getBoxNum(row, col);
            const num = board[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
    )
}

 

실제 스도쿠 판에 숫자를 입력하는 toggleNum 함수를 선언합니다. board에 num을 입력한 후 가로, 세로, 박스 Boolean 배열을 반전시킵니다. 특정 숫자를 입력하면서 다음 칸으로 이동하다 만약 더 이상 프로세스가 진행불가인 경우에 도달하면 다시 이전 상태로 되돌려야 하므로 true로 절대갑을 입력하지 않고 반전값을 입력합니다.

const toggleNum = (row, col, num) => {
    board[row][col] = num;
    const box = getBoxNum(row, col);

    rowUsed[row][num] = !rowUsed[row][num];
    colUsed[col][num] = !colUsed[col][num];
    boxUsed[box][num] = !boxUsed[box][num];
}

 

1~9까지 숫자를 순회하면서 board를 순회하는 재귀함수를 선언합니다. 탈출조건은 idx가 빈칸의 배열인 blanks의 길이와 같아지는 시점입니다. 스도쿠에 값을 입력하기 위해서는 유효성 검사를 통과해야 하고, 먼저 toggleNum 함수를 돌린 후 유효성 검사에 실패하는 경우 값을 다시 반전시키는 백트래킹 알고리즘을 사용합니다. 

 

 

 

[Backtracking] 백준 15651 N과 M 3단계 Node.js 구현하기

 

const recur = (idx, blanks, board) => {
    if(idx === blanks.length) return true;
    const[row, col] = blanks[idx];

    for(let num=1; num<10; num++){
        if(isValid(row, col, num) === true){
            toggleNum(row, col, num);

            if(recur(idx+1, blanks, board) === true){
                return true;
            }

            toggleNum(row, col, num);
        }
    }
    return false;
}

 

스도쿠 전체 소스(Node.js)

const readline = require('readline');
const { stdin : input, stdout : output, mainModule } = require('process');
const { get } = require('http');

const rl = readline.createInterface({input, output});
let count = 1;
const board = [];

const main =(board)=>{
    const N = board.length;
    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 blanks = [];
    const rowUsed = [];
    const colUsed = [];
    const boxUsed = [];
    const getBoxNum = (row, col) => boxes[row][col];


    for(let i=0; i<N; i++){
        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 box = getBoxNum(row, col);
                const num = board[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) => {
        board[row][col] = num;
        const box = getBoxNum(row, col);

        rowUsed[row][num] = !rowUsed[row][num];
        colUsed[col][num] = !colUsed[col][num];
        boxUsed[box][num] = !boxUsed[box][num];
    }

    const recur = (idx, blanks, board) => {
        if(idx === blanks.length) return true;
        const[row, col] = blanks[idx];

        for(let num=1; num<10; num++){
            if(isValid(row, col, num) === true){
                toggleNum(row, col, num);

                if(recur(idx+1, blanks, board) === true){
                    return true;
                }

                toggleNum(row, col, num);
            }
        }
        return false;
    }

    recur(0, blanks, board);

    
    return board.map(item=>item.join(' ')).join('\n');

}

rl.on('line', (line)=>{
    board.push(line.split(' ').map(item=>Number(item)));
    

    if(count === 9){
        console.log(main(board));
        rl.close();
    }
    count++;
    
})

rl.on('close', ()=>{
    process.exit();
})

 

 

제출 결과

 

 

[Algorithm] 힙 정렬(Heap Sort) 구현하기 Node.js/Javascript

 

[Algorithm] Ugly Number 구하기 (Node.js)

 

[Algorithm] 기수 정렬 계수 정렬 Node.js