[BOJ][Python][2580] 스도쿠 - 시간초과

[문제 및 출처]

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

2580번: 스도쿠

[어떻게 풀까?]

흠...일단 아직 백트래킹을 어떻게 쓰는지 감이 잘 안 잡혀서 아무 생각 없이 구현이라도 해봐자는 마음으로 코드를 작성해 보았다. 정말 비효율적인 코드라고 나도 생각한다. 그렇기에 시간초과가 걸리고 말았고 이에 대해 다시 공부해야겠다는 생각을 가지게 되었다.

[CODE]

COLUM, ROW = 9, 9
board = [[0 for i in range(COLUM)] for j in range(ROW)] 
for i in range(COLUM):
        board[i] = list(map(int, input().split()))

#더하면 45    

def 가로체크(): #성공!
    for i in range(COLUM):
        temp, cnt = 0, 0
        index = 0 
        for j in range(ROW):
            if board[i][j] == 0:
                cnt += 1
                index = j
            temp += board[i][j]

        ok = 45 - temp
        if cnt == 1 and 1<= ok <= 9:
            board[i][index] = ok
    
def 세로체크(): #성공!
    for j in range(ROW):
        temp, cnt, index = 0, 0, 0
        for i in range(COLUM):
            if board[i][j] == 0:
                cnt += 1
                index = i
            temp += board[i][j]
        
        ok = 45 - temp
        if cnt == 1 and 1 <= ok <= 9:
            board[index][j] = ok

def 사각형체크(): #성공!
    for I in range(3):
        for J in range(3):
            temp, cnt, index_x, index_y = 0, 0, 0, 0
            for i in range(I*3, I*3+3):
                for  j in range(J*3, J*3+3):
                    if board[i][j] == 0:
                        cnt += 1
                        index_x, index_y = j, i
                    temp += board[i][j]
            ok = 45 - temp
            if cnt == 1 and 1<= ok <=9:
                board[index_y][index_x] = ok


def one_set():
    cnt = 1
    while cnt != 0:
        cnt = 0
        for i in range(COLUM):
            if 0 in board[i]:
                cnt += 1
                가로체크()
                세로체크()
                사각형체크()
    
one_set()

for line in board:
    for num in line:
        print(num, end= " ")
    print()