백준_2580_스도쿠(백트래킹)

def check(deph, x):
    for i in range(9):
        if i != x and i != deph:
            if board[deph][x] == board[deph][i]:
                return False
            if board[deph][x] == board[i][x]:
                return False
    return True

def dfs(deph):
    global flag
    if deph == 9:
        for i in range(9):
            print(*board[i])
        flag = False

    if flag:
        if board[deph].count(0) == 0:
            dfs(deph+1)
        for i in range(9):
            for j in range(1, 10):
                if board[deph][i] == 0:
                    board[deph][i] = j
                    if check(deph, i):
                        dfs(deph)
                    board[deph][i] = 0

board = []
flag = True
for _ in range(9):
    board.append(list(map(int, input().split())))

dfs(0)

아쉽게도 시간 초과된 코드이다.

다른 분들의 코드를 보니 0인 값을 for문을 돌며서 찾는 것이 아니라 입력 받을 때 해당 정보를 따로 저장한다. 이렇게 하면 for문을 돌면서 찾을 때 보다 확실히 시간절약이 가능하다.

check 과정에서 가로, 세로만 확인하는 것이 아니라 3*3 크기의 사각형에서도 겹치는 값이 있는지 확인해야한다. 이에 해당하는 코드도 추가해서 재시도

def check(x, y, v):
    for i in range(9):
        if v == board[x][i]:
            return False
        if v == board[i][y]:
            return False
    for i in range(x//3 * 3, x//3*3 + 3):
        for j in range(y//3*3 , y//3*3 + 3):
            if v == board[i][j]:
                return False
    return True

def dfs(deph):
    global flag
    if deph == len(zeros):
        for i in range(9):
            print(*board[i])
        flag = False

    if flag:
        x = zeros[deph][0]
        y = zeros[deph][1]
        for j in range(1, 10):
            if check(x, y, j):
                board[x][y] = j
                dfs(deph+1)
                board[x][y] = 0

board = []
flag = True
zeros = []
for i in range(9):
    tmp = list(map(int, input().split()))
    board.append(tmp)
    for j in range(9):
        if tmp[j] == 0 :
            zeros.append([i,j])

dfs(0)

---

비록 0인 값을 따로 저장하는 개념은 다른 분들의 코드를 보면서 깨달았지만 나머지 부분은 직접 짜는데에 성공했다.