[JavaScript] 백준 2580 스도쿠 (JS)

스도쿠

📚 문제 설명

9 * 9 크기의 스도쿠 판이 있다고 한다.
스도쿠에 빈칸이 있고 빈칸은 아래와 같은 규칙으로 채워진다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

빈칸이 있는 스도쿠가 주어졌을 때 모든 빈 칸이 채워진 최종 모습을 출력하라.

👨🏻‍💻 풀이 과정

zero 에 우선 0의 위치를 모두 찾아서 저장해야 한다.
그 후 DFS문과 유사하게 만들어서 0위치에 값을 부여해주면 된다.

DFS문을 간략히 설명하면 zero를 하나씩 확인하며 값을 넣고 모든 0에 값을 채우면 종료되도록 했다.

DFS문 로직

• 인자(Index)로 zero 값 하나씩 확인.
• Index가 zero.length와 같다면 정답 출력.
• 1 ~ 9 중에 알맞은 값 넣기.
• 재귀를 통해 나머지 0도 채우기.
• 넣었던 값 0으로 다시 되돌리기.

전체 풀이

    let fs = require("fs");
    let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
    input = input.map(v => v.split(' ').map(e => parseInt(e)));
	// 0 좌표 모음.
    let zero = [];
	// 0좌표 찾기.
    function Find() {
        for (let i = 0; i < input[0].length; i++) {
            for (let j = 0; j < input.length; j++) {
                if (input[i][j] == 0) {
                    zero.push([i, j]);
                }
            }
        }
    }
    Find();
	// zero 채우기.
    function DFS(Index) {
        if (Index === zero.length) {
            console.log(input.map(v => v.join(' ')).join('\n'));
          	// 1개만 출력하고 바로 종료하기 위해.
            process.exit();
        }
        let zeroX = zero[Index][0];
        let zeroY = zero[Index][1];
      	// 1부터 9까지 숫자를 넣기.
        for (let i = 1; i < 10; i++) {
          	// 가능한지 확인.
            if (Check(zeroX, zeroY, i)) {
              	// 0을 i로 변경.
                input[zeroX][zeroY] = i;
              	// 다음 0을 찾아서 값 넣기.
                DFS(Index + 1);
              	// 넣어놨던 i 값을 다시 0으로 바꿈.
                input[zeroX][zeroY] = 0;
            }
        }
    }
	// x,y위치에 value를 넣을 수 있는지 확인.
    function Check(x, y, value) {
      	// 가로 새로 확인.
        for (let i = 0; i < input.length; i++) {
            if (input[i][y] === value || input[x][i] === value) return false;
        }
        let boxX = Math.floor(x / 3) * 3;
        let boxY = Math.floor(y / 3) * 3;
      	// 3 * 3 위치 확인.
        for (let i = boxX; i < boxX +3; i++) {
            for (let j = boxY; j < boxY + 3; j++) {
                if (input[i][j] === value) {
                    return false;
                }
            }
        }
        return true;
    }

    DFS(0);

🧐 후기

이 문제는 로직을 구현하고 제출했는데 계속 틀려서 일단 포기했다가 한 달 후에 다시 푼 문제이다.
한 달 후에 다시 코드를 천천히 살펴보니 정답 출력 부분이 정답 형식과 달랐고 zero 에서 좌표를 받았아서 zeroY에 저장하는 부분이 잘못되었었다. 이 부분을 수정하고 다시 제출하니 무사히 통과할 수 있었다.
때로는 코드를 차분하게 들여다보는 것도 매우 중요한 것 같다.