[백준] 2580번(스도쿠)

백준 2580번

✔️ 문제 풀이

처음 제출한 코드

def check(matrix, row, col, n):

  rstart = row//3
  cstart = col//3

  row_arr = [0]*10
  col_arr = [0]*10
  square_arr = [0]*10

  for i in range(9):
    row_arr[matrix[row][i]] = 1
  if row_arr[n] != 0:
    return False

  for i in range(9):
    col_arr[matrix[i][col]] = 1
  if col_arr[n] != 0:
    return False

  for i in range(3):
    for j in range(3):
      square_arr[matrix[rstart*3+i][cstart*3+j]] = 1
  if square_arr[n] != 0:
    return False

  return True

def dfs():

  for i in range(9):
    for j in range(9):
      if array[i][j] == 0:
        for k in range(1, 10):
          if check(array, i, j, k):
            print(i, j ,k)
            array[i][j] = k
            if sum(sum(array[i][j] for j in range(9)) for i in range(9)) == 45*9:
              return True
            if dfs():
              return True
            array[i][j] = 0


array = [list(map(int, input().split())) for i in range(9)]

dfs()

for i in range(9):
  print(*array[i])

◾ dfs로 풀이

• 시간초과
• 논리자체에는 문제가 없으나 시간효율을 개선해야함

✔️ 개선점

1 ) 유효성 검사

• 현재는 matrix의 값을 인덱스로 하는 배열을 만들어서, 행, 열, 3X3 사각형 범위를 모두 탐색하고,
• 배열의 값을 저장하는 배열을 또 만들어서 값을 할당하고 있음
  ⇒ 새로운 배열에 값을 할당하거나 모두 탐색할 필요 없이 탐색 중 n과 같은 값이 등장하면 바로 return False

2 ) 빈 칸 탐색

• 스도쿠의 크기는 9X9이어서 다음 빈칸을 찾기 위해 처음부터 다시 탐색한다고 해서 많은 시간이 소요되지 않을 것이라고 생각했으나, 빈칸이 많아질수록 이에 대한 가중이 커짐(많은 연산이 필요함으로)
  ⇒ 배열을 입력받을 때 값이 0인 칸의 좌표값을 저장하는 배열을 생성
  ⇒ dfs 탐색 시, 배열을 처음부터 탐색하지 않아도 되고, index 전달을 통해 탐색해야 할 좌표를 바로 구할 수 있으므로 시간 단축

✔️ 문제점 개선한 풀이

수정한 코드

def row(x, n):
  for i in range(9):
    if matrix[x][i] == n:
      return False
  return True

def col(y, n):
  for i in range(9):
    if matrix[i][y] == n:
      return False
  return True

def squre(x, y, n):
  xstart = x//3*3
  ystart = y//3*3
  for i in range(3):
    for j in range(3):
      if matrix[xstart+i][ystart+j] == n:
        return False
  return True

def dfs(index):

  if index == len(blank):
    for i in range(9):
      print(*matrix[i])
    exit()
    
  for i in range(1, 10):
    x = blank[index][0]
    y = blank[index][1]
    if row(x, i) and col(y, i) and squre(x, y, i):
      matrix[x][y] = i
      dfs(index+1)
      matrix[x][y] = 0
      
matrix = []
blank = []

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

dfs(0)

❗수정된 코드도 Python3에서는 시간초과가 뜬다. PyPy3에서만 정답 처리

참고코드