[JS][백준]2239_스도쿠

문제 번호

2239번: 스도쿠

 

 

 

알고리즘 분류

• 구현
• 백트래킹

 

문제 풀이

 스도쿠다. 

전에 C++ 로 스도쿠문제를 풀어본적이 있는데 백준에는 스도쿠 문제가 여러개 있다. 

하지만 그떄랑 푸는 방법은 크게 다르지않다. 알고리즘은 어렵지않다. 

 문제에서 주어지는 스도쿠 게임판을 입력받고 '0'으로 표기된 빈자리가 발견될 때 마다 해당 자리에 1부터 9까지의 수를 모두 넣어보면서 정답이 나올때 까지 찾아보면된다. 문제에서 정답이 여러개일 경우 가장 작은자리를 정답으로 처리한다 하였으니 1부터 9의 순서로 넣도록 하자.

 스도쿠 게임판을 탐색하다가 0을 발견하면 해당자리에 1부터 9의 수를 차례로 넣어가면서 해당자리에 적합한 숫자인지 check라는 함수로 확인한다. 이때 check 함수는 가로, 세로, 사각형을 모두 검사한다. 사각형을 확인할때는 0이 발견된 좌표를 다음과 같이 처리한다.

  // 사각형 확인.
  x = parseInt((x / 3)) * 3;
  y = parseInt((y / 3)) * 3;

 

만약 check라는 함수를 통해서 해당 숫자가 부적합하다는 결과가 return된다면 해당자리를 다시 0으로 되돌려놓고 다음숫자를 넣어본다.

 만약 9까지 넣어봤는데도 실패했다면 해당칸 이전에 넣었던 숫자가 옳지않은 숫자인것이다. 따라서 9까지 실패했다면 즉시 return 하여 이전단계의 숫자를 바꿔주는 과정을 거친다.

 

 스도쿠 게임판을 입력받을때 0의 개수를 세어서 총 몇개의 자리를 채워넣어야 스도쿠가 완성되는지 확인하기로 하였다. 그래서 blank 라는 변수를 사용해서 0의 개수를 세어주었다. 그리고 blank가 0이되면 스도쿠 게임판을 출력해주고 end라는 변수를 true로 바꿔줌으로써 여러가지 경우의 완성된 게임판이 출력되는것을 방지하였다. (end 변수를 통하여 제어해주지 않으면 모든 칸이 0 으로 이루어진 스도쿠 게임판이 입력으로 들어올때 매우 많은 완성된 스도쿠들을 출력하게 된다.)

 if(blank === 0){
    print(sudoku);
    end = true;
  }
  if(end)
    return 0;

 

전체코드

let end = false;

function print(sudoku){
  let answer = ''    
  for(let i=0; i<9; i++){    
    for(let j=0; j<9; j++){
      answer += sudoku[i][j];
    }
    answer +='\n'
  }
  console.log(answer.trim());  
}

function check(x, y, sudoku, k) {
  // 가로 확인
  for (let i = 0; i < 9; i++)
    if (sudoku[y][i] === k)
      return false;
  // 세로 확인
  for (let i = 0; i < 9; i++)
    if (sudoku[i][x] === k)
      return false;
  // 사각형 확인.
  x = parseInt((x / 3)) * 3;
  y = parseInt((y / 3)) * 3;
  for (let i = y; i < y + 3; i++) {
    for (let j = x; j < x + 3; j++) {
      if (sudoku[i][j] === k)
        return false;
    }
  }
  return true;
}

function sol(sudoku, blank) {
  if(blank === 0){
    print(sudoku);
    end = true;
  }
  if(end)
    return 0;

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {

      // 비어있는 자리를 발견하면.
      if (sudoku[i][j] === 0) {
        // 1부터 9까지 넣어본다.
        for (let k = 1; k <= 9; k++) {          
          if (check(j, i, sudoku, k)) {            
            sudoku[i][j] = k;
            sol(sudoku, blank-1);
            sudoku[i][j] = 0;
          }          
          if(k===9)
            return;
        }
      }
    }    
  }  
}

function insert() {
  const input = require('fs').readFileSync('2239_스도쿠/input.txt').toString().split('\n');
  let sudoku = new Array(9).fill(null).map(_ => new Array(9).fill(0));
  let blank = 0;
  for (let i = 0; i < 9; i++) {
    let row = input[i].split('').map(Number);
    for (let j = 0; j < 9; j++) {
      if(row[j] === 0)
        blank++;
      sudoku[i][j] = row[j];
    }
  }
  sol(sudoku,blank);
  //  console.log(sudoku);
}

insert();

특이사항

 C++ 로 풀이했을때 보다 함수들을 더 잘 나눠서 푼것같다. 

사각형을 확인하는 과정에서 좌표처리를 어떻게 해야할지 몰라서 전에 풀었던 풀이를 참고했다.