[BOJ 백준] 2580번 : 스도쿠(Python, 파이썬)

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

 

백트래킹을 활용하는 문제였다. 스페셜 저지이므로, 답이 여러개 나올 수 있다.

 

3x3으로 처리된 부분을 어떤식으로 검사 해야할 지 아이디어가 잘 안떠올랐다.

 

 

구현 로직

 

• 입력받은 스도쿠에서 0이 들어간 곳의 좌표를 따로 저장한다
• 0이 있는 위치에 들어갈 수 있는 후보 숫자들을 리스트에 저장한다
  • 1부터 9까지 저장된 리스트(numbers)를 생성한다.
  • 스도쿠 전체를 탐색하며 행, 열, 3x3 배열에 있는 0이 아닌 숫자를 리스트에서 제거한다.
    • cf) 3x3 배열을 탐색하는 방법은 다음과 같다
    • 인덱스 별로 (0~2), (3~5), (6~8)이 같은 그룹으로 묶인다. 그렇기 때문에 y좌표와 x좌표를 3으로 나눈 몫에 다시 3을 곱하면 그 그룹에서 시작하는 인덱스 값을 알 수 있다.
    • 예를 들어 (5,2)에 들어가는 값은 (5//3, 2//3) 이므로 (1,0) 에서 각각 3을 곱하면 (3,0)이다. 즉 좌상단이 (3,0)이고 우하단이 (5,2)까지인 3x3인 배열에 대해 탐색을 진행해야 한다.
  • 숫자가 제거되고 남은 리스트를 리턴한다.
• 리턴받은 리스트가 해당 지점(원래 0이었던 점)에 들어갈 수 있는 숫자의 후보다.
• 이 리스트를 순회하면서 해당 지점에 숫자를 넣었다가 뺴보는 백트래킹 방식으로 dfs 탐색을 진행한다.

 

 

소스코드

  import sys
  #sys.stdin = open("input.txt", "r")
  board = [list(map(int, input().split())) for _ in range(9)]
  emptySpace = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]


  def candidating(y, x):  # 빈칸에 들어갈 수 있는 숫자 후보 : 스도쿠 규칙에 따라 가로,세로,3x3 칸 내에 겹치는 숫자가 없어야 함
      numbers = [i+1 for i in range(9)]
      # 행 / 열 검사
      for k in range(9):
          if board[y][k] in numbers:
              numbers.remove(board[y][k])
          if board[k][x] in numbers:
              numbers.remove(board[k][x])
      # 3*3 검사
      y = y//3
      x = x//3
      for i in range(y*3, (y+1)*3):
          for j in range(x*3, (x+1)*3):
              if board[i][j] in numbers:
                  numbers.remove(board[i][j])
      return numbers


  def dfs(count):
      if count == len(emptySpace):
          for row in board:
              print(*row)
          return
      (i, j) = emptySpace[count]
      candi = candidating(i, j)  # 빈칸에 들어갈 수 있는 숫자 후보
      for num in candi:
          board[i][j] = num
          dfs(count+1)
          board[i][j] = 0


  dfs(0)

 

 

 

좀 더 깔끔한 코드

  def dfs(depth):
      if depth == blank_num:
          for v in board:
              print(' '.join(map(str, v)))
          exit(0)

      y, x = pos[depth]
      for n in range(1, 10):
          if not row_arr[y][n] and not col_arr[x][n] and not box_arr[y//3*3+x//3][n]:
              row_arr[y][n] = col_arr[x][n] = box_arr[y//3*3+x//3][n] = True
              board[y][x] = n
              dfs(depth+1)
              row_arr[y][n] = col_arr[x][n] = box_arr[y//3*3+x//3][n] = False
              board[y][x] = 0

  board = [list(map(int, input().split())) for _ in range(9)]
  row_arr = [[False]*10 for _ in range(10)]
  col_arr = [[False]*10 for _ in range(10)]
  box_arr = [[False]*10 for _ in range(10)]

  pos = []
  for r in range(9):
      for c in range(9):
          if not board[r][c]: pos.append([r, c])
          else:
              row_arr[r][board[r][c]] = True
              col_arr[c][board[r][c]] = True
              box_arr[r//3*3+c//3][board[r][c]] = True

  blank_num = len(pos)
  dfs(0)