[JS] 백준 2580번 : 스도쿠 - 백트래킹, DFS

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

2580번: 스도쿠

 

 

풀이방법

1. 스고쿠 맵안에서 0인 곳의 좌표를 모두 찾아 저장한다.

2. DFS를 호출해 카운트 0부터 시작한다 

 -이는 0인 곳에 숫자를 넣은 후 +1해서 다시 DFS를 재귀호출한다.

3. DFS를 0부터 시작했으므로 0인 곳의 좌표를 저장했던 배열도 인덱스 0부터 시작한다.

 -0인 곳의 좌표를 순차적으로 뽑아내서 그 안에 숫자를 넣을 것이다.

4. 1 ~ 9까지의 숫자를 모두 넣어보고 가로열, 세로열, 3*3 부분에서 스도쿠가 성사되는지 확인한다.

5. 만약 성사된다면 map안에 그 값을 넣고 DFS를 count+1해서 재귀호출한다.

6. 이후 만약 해당 재귀호출이 어느 숫자에서 성사되지않는다면 백트래킹을 위해 다시 map에 숫자를 넣었던 좌표를 다시 0으로 만들어준다.

7. 이렇게 재귀호출을 뻗어나가면서 만약 성공적으로 0인 곳의 좌표에 모두 숫자를 넣었다면 스도쿠가 성사된 것이므로 해당 map을 출력하고 프로그램을 종료한다.

 

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let map = [];
for (var i = 0; i < 9; i++) {
  map[i] = input[i].split(" ").map(Number);
}
let arr = [];
for (var i = 0; i < 9; i++) {
  for (var j = 0; j < 9; j++) {
    if (map[i][j] === 0) {
      arr.push([i, j]);
    }
  }
}

let check = (y, x, value) => {
  //가로 줄에서 같은 숫자 있는지
  for (let i = 0; i < 9; i++) {
    if (map[y][i] == value) return false;
  }
  //세로 줄에서 같은 숫자있는지
  for (let i = 0; i < 9; i++) {
    if (map[i][x] == value) return false;
  }

  //3*3도 맞는지
  let threeX = Math.floor(x / 3) * 3;
  let threeY = Math.floor(y / 3) * 3;

  for (let i = threeY; i < threeY + 3; i++) {
    for (let j = threeX; j < threeX + 3; j++) {
      if (map[i][j] == value) return false;
    }
  }
  return true;
};

let DFS = (count) => {
  if (count == arr.length) {
    console.log(map.map((v) => v.join(" ")).join("\n"));
    process.exit(0);
  }

  let [y, x] = arr[count];

  //숫자 1~9를 그냥 넣어서 맞는지 확인
  for (let i = 1; i < 10; i++) {
    if (check(y, x, i)) {
      map[y][x] = i;
      DFS(count + 1);
      map[y][x] = 0;
    }
  }
};
DFS(0);

 

 

💢어려웠던 점

1. DFS의 기준을 어떻게 잡을지 파악하지 못했다.

-가로열 세로열 3*3부분을 확인하고 재귀로 뻗어나가야 하는데 1~9까지 모든 수를 넣어보면서 확인하는 방법을 생각하지 못했다.

-그저 가로열 세로열 3*3 확인해서 정답인 숫자를 넣는다는 생각만했다.