36. Valid Sudoku

36. Valid Sudoku

문제

올바른 스도쿠인지 확인해보자!

스도쿠는 즐겨하는 게임이어서 코드로 접근하는 것도 재밌었다. 2차원 배열의 9*9 배열이 주어진다. 스도쿠의 기본 룰에 따라 1*9 가로줄, 9*1세로줄, 3*3서브 박스에 1-9까지 숫자가 한번씩만 들어간다. 주어진 board에 미리 채워진 숫자가 규칙에 맞는지 확인한다.

👉 유효한 스도쿠인지 확인하는 것이 아니라, 미리 채워진 숫자가 유효한지만 확인한다.

테스트 케이스

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

풀이

즉각적으로 떠오른 방법은 모든 board를 탐색하면서 해당 셀의 숫자를 행, 열, 박스 인덱스에 Set()으로 저장하고 중복되는 숫자가 있는지 확인하는 방법이다. 박스 인덱스를 구하는 것이 관건이다. 박스 인덱스는 윗 줄부터 0,1,2 3,4,5 6,7,8인데, Math.floor(row / 3) * 3 + Math.floor(col / 3) 공식으로 구할 수 있다.

var isValidSudoku = function(board) {
  const rows = new Array(9).fill(0).map(() => new Set())
  const cols = new Array(9).fill(0).map(() => new Set())
  const boxes = new Array(9).fill(0).map(() => new Set())

  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      const n = board[row][col];
      if (n === ".") continue;

      const box = Math.floor(row / 3) * 3 + Math.floor(col / 3)
      if (rows[row].has(n) || cols[col].has(n) || boxes[box].has(n)) {
        return false;
      }

      rows[row].add(n)
      cols[col].add(n)
      boxes[box].add(n)
    }
  }
  
  return true;
};

---

이제 본격적으로 스도쿠를 풀어볼까?
👉 다음 문제는 Sudoku Solver