[BOJ 2239번] : 스도쿠

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

2239번: 스도쿠

이 코드만 있으면 동아일보 스도쿠의 왕이 될 것 같네요!
풀이는 인터넷을 참고해 다음 순서대로 구현했습니다.

1. 값이 0인 지점에 숫자를 대입하고(방문 표시), 행 / 열 / 해당 지점이 속한 3 * 3 공간에 1 ~ 9가 모두 들어 있는지 검사합니다.
2. 만약 모든 검사를 통과했다면 다음 0을 찾아 1단계의 검사를 반복합니다.
3. 만약 검사에 걸렸다면, 해당 지점의 숫자를 다시 0으로 바꾸고 리턴합니다. (이전 단계로 돌아갑니다!)

import sys
import time
input = sys.stdin.readline
board = []

for _ in range(9):
    temp = input().rstrip()
    tempList = []
    for i in temp:
        tempList.append(int(i))
    board.append(tempList)


def checkAreaComplete(row, col):
    count = [0] * 10
    for i in range(row // 3 * 3, row // 3 * 3 + 3):
        for j in range(col // 3 * 3, col // 3 * 3 + 3):
            if board[i][j] > 0:
                count[board[i][j]] += 1
                if count[board[i][j]] > 1:
                    return False
    return True


def checkColumnComplete(row):
    count = [0] * 10
    for col in range(9):
        if board[row][col] > 0:
            count[board[row][col]] += 1
            if count[board[row][col]] > 1:
                return False
    return True


def checkRowComplete(col):
    count = [0] * 10
    for row in range(9):
        if board[row][col] > 0:
            count[board[row][col]] += 1
            if count[board[row][col]] > 1:
                return False
    return True


def dfs(startNode):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for number in range(1, 10):
                    board[row][col] = number
                    if checkAreaComplete(row, col) and checkRowComplete(col) and checkColumnComplete(row):
                        dfs((row, col))
                    board[row][col] = 0
                return
            if row == 8 and col == 8:
                for i in range(9):
                    for j in range(9):
                        if board[i][j] == 0:
                            return
                for row in board:
                    for col in row:
                        print(col, end="")
                    print()

                # print("--- %s seconds ---" % (time.time() - start_time))
                exit()


# start_time = time.time()

dfs((0, 0))

처음 작성한 풀이는 위와 같았습니다.
그런데 계속해서 시간 초과가 나 파이썬으로 문제를 푼 다른 분의 코드를 참고해보니, 검사 로직을 각각 분리하면 시간 초과가 나 배열 등을 활용해 저걸 한번에 검사해줘야 하는 것 같았습니다.

다른 고수의 코드

import sys
import time
input = sys.stdin.readline


def dfs(cnt):
    if cnt == 81:
        for row in board:
            for col in row:
                print(col, end="")
            print()
        # print("--- %s seconds ---" % (time.time() - start_time))
        exit()
    else:
        row = cnt // 9
        col = cnt % 9
        square = (row // 3) * 3 + col // 3
        if board[row][col] == 0:
            for num in range(1, 10):
                if not (columnCheck[col][num] or rowCheck[row][num] or squareCheck[square][num]):
                    columnCheck[col][num] = True
                    rowCheck[row][num] = True
                    squareCheck[square][num] = True
                    board[row][col] = num
                    dfs(cnt + 1)
                    board[row][col] = 0
                    columnCheck[col][num] = False
                    rowCheck[row][num] = False
                    squareCheck[square][num] = False

        else:
            dfs(cnt + 1)


board = []

columnCheck = [[False for _ in range(10)] for _ in range(9)]
rowCheck = [[False for _ in range(10)] for _ in range(9)]
squareCheck = [[False for _ in range(10)] for _ in range(9)]

for row in range(9):
    temp = list(map(int, list(input().rstrip())))
    for col in range(9):
        if temp[col] != 0:
            square = (row // 3) * 3 + col // 3
            columnCheck[col][temp[col]] = True
            rowCheck[row][temp[col]] = True
            squareCheck[square][temp[col]] = True
    board.append(temp)

# start_time = time.time()

dfs(0)

실제로 고수분의 코드를 돌려보니 시간이 약 1/10까지 단축된 것을 알 수 있었는데요, 이런 식으로 코드의 최적화도 많이 신경써야 하는 것을 느낄 수 있었습니다...