백준 _ 2580 스도쿠 (Python, JavaScript)

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

 

풀이 과정

1. 빈 칸의 좌표를 모두 조회해 보관한다.

2. 빈 칸에 들어갈 수 있는 숫자를 체크해본다. 이때, 행/열/정사각형 범위를 체크한다.

3. DFS 백트래킹을 통해 모든 빈 칸의 좌표가 채워질 때까지 반복한다.

 

Python 코드

def check(y, x, n):
  for i in range(9):
    if n == arr[y][i] or n == arr[i][x]:
      return False

  for i in range(3):
    for j in range(3):
      if n == arr[y//3 * 3 + i][x//3 * 3 + j]:
        return False
  return True


def find(n):
  if n == len(blank):
    for ar in arr:
      print(*ar)
    exit()

  for i in range(1, 10):
    y, x = blank[n]
    if check(y, x, i):
      arr[y][x] = i
      find(n+1)
      arr[y][x] = 0


arr = [list(map(int, input().split())) for _ in range(9)]
blank = []
for i in range(9):
  for j in range(9):
    if arr[i][j] == 0:
      blank.append([i, j])
find(0)

 

JavaScript 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')

const check = (y, x, n) => {
  for (let i=0; i<NINE; i++) {
    if (n == arr[y][i] || n == arr[i][x]) {
      return false
    }
  }
  for (let i=0; i<THREE; i++) {
    for (let j=0; j<THREE; j++) {
      yIdx = Math.floor(y/3) * 3 + i
      xIdx = Math.floor(x/3) * 3 + j

      if (n == arr[yIdx][xIdx]) {
        return false
      }
    }
  }
  return true
}

const find = (n) => {
  if (n == blank.length) {
    arr.forEach(ar => {
      console.log(ar.join(' '))
    })
    process.exit()
  }

  for (let i=1; i<=NINE; i++) {
    const [y, x] = blank[n]
    if (check(y, x, i)) {
      arr[y][x] = i
      find(n+1)
      arr[y][x] = 0
    }
  }
}

const THREE = 3
const NINE = 9
const arr = input.map(line => line.split(' ').map(Number))
const blank = []
for (let i=0; i<NINE; i++) {
  for (let j=0; j<NINE; j++) {
    if (arr[i][j]) continue
    blank.push([i, j])
  }
}
find(0)

 

특별히 유의해야할 포인트는

스도쿠 판을 다 채웠다면 더 돌아보지 않고 프로그램을 종료해 답을 내야하기 때문에

return으로 함수를 끝내지 않고 exit()를 사용했다는 점이다.

 

exit 하지 않고 return을 하게 되면 종료조건인 n == blank.length 에서

return 되어도 재귀함수가 완전히 끝나지 않고 다시 n=9가 되었다가 다시 return 되는 과정이 반복되며

무한루프에 빠지게 된다. 채점 시 29%에서 틀렸습니다를 만날 수 있다.😇

 

---

요즘 여러 알고리즘 문제 꾸준히 풀고 있지만

스도쿠는 특별히 좋아하는 게임(?) 이라 굳이 글을 올려보았다.

 

나는 스도쿠 푸는 것을 꽤 좋아하고 잘 푸는 편이지만

코드로 구현하기 위해 접근하는 것은 꽤나 어려웠다 ... 

.. 알고리즘 잘 하고 싶다 ....