2580. 스도쿠

 

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

 

참고로 문법은 python2, 제출은 pypy2로 했다.

python3으로 하니 시간 초과가 났다.

주요 아이디어는 zero라는 리스트에 값이 0인 것들의 행렬을 튜플로 저장해놓은 것이고,

또 작은 사각형에 중복된 숫자가 있는지 검사할 때

속하는 작은 사각형의 범위를 (row//3)*3, (col//3)*3으로 표현한 것이다.

이것만이 정답은 아니지만 프로그래밍을 할 때

'무언가 정보를 담을 새로운 공간'를 떠올려 보는 것도 좋을 것 같다.

 

import sys
r = sys.stdin.readline

board = []
for i in range(9):
    board.append(list(map(int, r().split())))

zero = []
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            zero.append((i, j))

def Print():
    for row in range(9):
        for col in range(9):
            print board[row][col],
        print("")

def isPossible(num, row, col):
    if num in board[row]:
        return False
    for i in range(9):
        if num == board[i][col]:
            return False
    row_t = row // 3 * 3
    col_t = col // 3 * 3
    for r in range(row_t, row_t + 3):
        for c in range(col_t, col_t + 3):
            if num == board[r][c]:
                return False
    return True

def dfs(zeroIndex):
    if zeroIndex == len(zero):
        Print()
        exit(0)
    for num in range(1, 10):
        row = zero[zeroIndex][0]
        col = zero[zeroIndex][1]
        #print("row col: {} {}".format(row, col))
        if isPossible(num, row, col):
            board[row][col] = num
            dfs(zeroIndex+1)
        board[row][col] = 0

dfs(0)