스도쿠

문제설명

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

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

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다.
스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

예제 입력 1             예제 출력 1
0 3 5 4 6 9 2 7 8     1 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9     7 8 2 1 3 5 6 4 9
0 6 0 2 7 8 1 3 5     4 6 9 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7     3 2 1 5 4 6 8 9 7
8 0 4 9 1 3 5 0 6     8 7 4 9 1 3 5 2 6
5 9 6 8 2 0 4 1 3     5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 0 8 0     9 1 7 6 5 2 3 8 4
6 0 3 7 0 1 9 5 2     6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 0     2 5 8 3 9 4 7 6 1

문제 설명

1. 가로, 세로, 사각형에 존재하는 숫자들을 판별하기 위한 변수 선언.(10까지 하는 이유는 0은 안쓰고 1~9까지만 사용.)
2. 받은 input에서 0이 아닌 숫자들만 true로 바꿈. 주어진 좌표를 받았을때, 가로(i) 세로(j)는 각 숫자 자리를 true로 바꾸면 된다.
   (ex. 1,7 에 3을 넣고 싶으면 hor[1][3],ver[7][3]을 확인. 만약 하나라도 true라면 그 자리에는 3이 들어갈 수 없음). 또, 사각형 또한 조사해줘야하는데, 좌표 1,7이 들어왔을 때, 사각형의 위치를 알아야하는데
   1,7의 경우 위의 사각형에서 2번째 사각형에 속한다. 이렇게 어느 사각형에 속하는지 알아야하기 하는데,
   이를 구하기 위해서는 x/3 * 3 + y/3(둘 다 소숫점은 버린상태로 해야함)을 해주면, 어느 좌표가 어떤 사각형에 속하는지 알 수 있다.
   이것을 이용해서 rec배열을 초기화시켜준다.
3. dfs를 이용해서 탐색해야하는데, count를 세주는데, count를 이용해서 x,y좌표를 구한다.
4. x는 count/9의 소숫점 제외, y는 count/9의나머지로 하면 (0,0)부터 (8,10)까지의 모두 다 확인할 수 있다.
5. 이렇게 모든 좌표를 확인하는데, input[x][y]가 0인 것들만 확인하면 되니까 if문으로 처리.
   이제 input[x][y]가 0이면, 숫자를 골라서 집어넣어야하는데, hor,ver,rec배열에서 false의 값들만 가능하다.
   (ex. (3,9)의 좌표가 0이라고 하면, 3번째 행과, 9번째 열을 확인하고, (3,9)좌표가 속하는 사각형도 살펴봐야한다.)
   모든 값이 false여서 선택할 수 있는 숫자라고 하면, input[x][y]를 선택된 숫자로 바꿔주고 hor,ver,rec을 모두 바꿔준다.
   여기서 중요한 포인트는 dfs를 다시 호출한 뒤 값을 초기화 시켜주는 것인데, 만약에 고른 숫자가 잘못된 숫자인 경우가 있을 수 있으므로,
   다른 값을 찾기 위해서 초기화 시켜서 다시 진행해야한다.(백트래킹 과정)
   이러한 과정을 거쳐서 count가 81(9*9니까)이 되면 print한다.
   근데 여러가지 경우가 있을 수 있으므로 process.exit(0)을 통해 해당 프로세스를 종료한다.

var fs = require("fs");
// var input = fs.readFileSync("/dev/stdin").toString().split("\n");
var input = fs.readFileSync("./stdin").toString().split("\n");
input = input.map(e => e.split(" "));
const hor = Array.from(Array(9), () => Array(10).fill(false));
const ver = Array.from(Array(9), () => Array(10).fill(false));
const rec = Array.from(Array(9), () => Array(10).fill(false));
for (let i = 0; i < 9; i++) {
  for (let j = 0; j < 9; j++) {
    if (input[i][j] !== "0") {
      hor[i][input[i][j]] = true;
      ver[j][input[i][j]] = true;
      rec[Math.floor(i / 3) * 3 + Math.floor(j / 3)][input[i][j]] = true;
    }
  }
}

dfs(0);

function dfs(count) {
  let x = Math.floor(count / 9);
  let y = count % 9;

  if (count === 81) {
    input.forEach(e => {
      let total = "";
      e.forEach((el, idx) => {
        if (idx === 0) total += el;
        else total += ` ${el}`;
      });
      console.log(total);
    });
    process.exit(0);
  }

  if (input[x][y] === "0") {
    for (let i = 1; i <= 9; i++) {
      if (
        hor[x][i] === false &&
        ver[y][i] === false &&
        rec[Math.floor(x / 3) * 3 + Math.floor(y / 3)][i] === false
      ) {
        input[x][y] = String(i);
        hor[x][i] = true;
        ver[y][i] = true;
        rec[Math.floor(x / 3) * 3 + Math.floor(y / 3)][i] = true;
        dfs(count + 1);
        input[x][y] = "0";
        hor[x][i] = false;
        ver[y][i] = false;
        rec[Math.floor(x / 3) * 3 + Math.floor(y / 3)][i] = false;
      }
    }
  } else {
    dfs(count + 1);
  }
}

아쉬운 점 || 느낀 점

처음에 접근 방식이 아예 틀렸었다.
백트래킹을 잘 몰라서 아예 다른 방향으로 풀다가 구글링으로 해결.(심지어 구글링도 이해못해서 엄청오래걸림) 그래도 이번 기회에 백트래킹에 대해서 조금 이해한 것 같으니 다른 문제가 나오면 시도정도는 해볼 수 있을 것 같다.
백준 같은 경우는 프로그래머스보다 더 어려운 느낌이여서 프로그래머스를 풀고 있지만,
친구 덕분에 문제를 풀어볼 수 있었고, 같이 문제를 푸니까 동지(?)가 있는 기분이라 스트레스를 덜 받는 것 같다.