2580 스도쿠 (자바스크립트)

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

문제 분석

입력으로 스도쿠가 주어졌을 때, 알맞은 숫자가 들어간 정답을 출력하는 문제이다.

각 칸 별로 가능한 모든 숫자들을 넣어보는 브루트포스 문제이다.

우선 빈칸(gr[i][j] 가 0)인 좌표들을 모두 구해서 배열에 넣어본다.

let answer = 0;
    const coordinate = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (gr[i][j] === 0) {
                answer++;
                coordinate.push([i, j]);
            }
    }
}

이 빈칸들을 하나하나 탐색해가면서 행,열,사각형(3*3)을 탐색해가면서 가능한 숫자들을 구해보고 가능한 숫자가 있다면 그 다음 좌표를 탐색하는 dfs 방식을 사용했다.

const dfs = (coordiIdx, cnt) => {
    if (cnt === answer) {
        console.log(gr.map((v) => v.join(' ')).join('\n'));
        process.exit(0);
    }

    const [i, j] = coordinate[coordiIdx + 1];
    const possibleNumber = findPossibleNumbers(i, j, gr);
    if (possibleNumber.length === 0) return;
    for (const num of possibleNumber) {
        gr[i][j] = num;
        dfs(coordiIdx + 1, cnt + 1);
        gr[i][j] = 0;
    }
};

이때 가능한 숫자들을 찾아보는 것은 아래 함수이다.

const findPossibleNumbers = (x, y, gr) => {
    const numbers = Array.from({ length: n }, () => false);
    for (let j = 0; j < n; j++) {
        if (gr[x][j] === 0) continue;
        numbers[gr[x][j] - 1] = true;
    }
    for (let i = 0; i < n; i++) {
        if (gr[i][y] === 0) continue;
        numbers[gr[i][y] - 1] = true;
    }
    const r = Math.floor(x / 3) * 3;
    const c = Math.floor(y / 3) * 3;
    for (let i = r; i < r + 3; i++) {
        for (let j = c; j < c + 3; j++) {
            if (gr[i][j] === 0) continue;
            numbers[gr[i][j] - 1] = true;
        }
    }
    const num = [];
    for (let i = 0; i < n; i++) {
        if (!numbers[i]) {
            num.push(i + 1);
        }
    }
    return num;
}

정답 코드

const n = 9;

const findPossibleNumbers = (x, y, gr) => {
    const numbers = Array.from({ length: n }, () => false);
    for (let j = 0; j < n; j++) {
        if (gr[x][j] === 0) continue;
        numbers[gr[x][j] - 1] = true;
    }
    for (let i = 0; i < n; i++) {
        if (gr[i][y] === 0) continue;
        numbers[gr[i][y] - 1] = true;
    }
    const r = Math.floor(x / 3) * 3;
    const c = Math.floor(y / 3) * 3;
    for (let i = r; i < r + 3; i++) {
        for (let j = c; j < c + 3; j++) {
            if (gr[i][j] === 0) continue;
            numbers[gr[i][j] - 1] = true;
        }
    }
    const num = [];
    for (let i = 0; i < n; i++) {
        if (!numbers[i]) {
            num.push(i + 1);
        }
    }
    return num;
};

const main = (gr) => {
    let answer = 0;
    const coordinate = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (gr[i][j] === 0) {
                answer++;
                coordinate.push([i, j]);
            }
        }
    }

const dfs = (coordiIdx, cnt) => {
    if (cnt === answer) {
        console.log(gr.map((v) => v.join(' ')).join('\n'));
        process.exit(0);
    }

    const [i, j] = coordinate[coordiIdx + 1];
    const possibleNumber = findPossibleNumbers(i, j, gr);
    if (possibleNumber.length === 0) return;
    for (const num of possibleNumber) {
        gr[i][j] = num;
        dfs(coordiIdx + 1, cnt + 1);
        gr[i][j] = 0;
    }
};

    dfs(-1, 0);
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const gr = input.map((v) => v.split(' ').map((v) => +v));
main(gr);