[Python] 백준 2580번: 스도쿠

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

2580번: 스도쿠

import sys
input = sys.stdin.readline


def getBlankPositions():
    blankPositions = []

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

    return blankPositions


def dfs(blankIndex):
    global board

    if blankIndex == len(blankPositions):
        if isBoardAvailable():
            printBoard()
            return True
        else:
            return False

    blankX, blankY = map(int, blankPositions[blankIndex])
    possibleNumbers = getPossibleNumbers(blankX, blankY)

    for n in possibleNumbers:
        board[blankX][blankY] = n
        if dfs(blankIndex+1) == True:
            return True
        board[blankX][blankY] = 0


def getPossibleNumbers(x, y):
    isPossibleNumber = [True]*10

    # 가로 세로
    for i in range(9):
        isPossibleNumber[board[x][i]] = False
        isPossibleNumber[board[i][y]] = False

    # 섹터
    lineX, lineY = x//3, y//3
    for i in range(3):
        for j in range(3):
            curX, curY = 3*lineX+i, 3*lineY+j
            isPossibleNumber[board[curX][curY]] = False

    possibleNumbers = []
    for i in range(1, 10):
        if isPossibleNumber[i]:
            possibleNumbers.append(i)

    return possibleNumbers


def isBoardAvailable():
    # 가로
    for i in range(9):
        isNumbersAppeared = [False]*10
        for j in range(9):
            if isNumbersAppeared[board[i][j]] != False:
                return False
            isNumbersAppeared[board[i][j]] = True

    # 세로
    for i in range(9):
        isNumbersAppeared = [False]*10
        for j in range(9):
            if isNumbersAppeared[board[j][i]] != False:
                return False
            isNumbersAppeared[board[j][i]] = True

    # 섹터
    for i in range(3):
        for j in range(3):
            lineX, lineY = i, j
            isNumbersAppeared = [False]*10

            for k in range(3):
                for l in range(3):
                    curX, curY = 3*lineX+k, 3*lineY+l
                    if isNumbersAppeared[board[curX][curY]] != False:
                        return False
                    isNumbersAppeared[board[curX][curY]] = True

    return True


def printBoard():
    for i in range(9):
        for j in range(9):
            print(board[i][j], end=" ")
        print()


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

blankPositions = getBlankPositions()
dfs(0)

우선 빈 좌표들을 getBlankPositions()를 통해 blankPositions에 가져온다.

 

이후에 dfs + 백트래킹으로 탐색을 하는데, 이 때 blankIndex 인자를 증가시켜가면서 blankPositions를 모두 돈다.

베이스 케이스부터 설명하자면, 만약 blankIndex가 범위를 넘어간다는 것(blankIndex == len(blankPositions)은, 빈칸을 전부 채웠다는 뜻이므로, 현재의 board가 스도쿠의 정답일 경우 True를 리턴해준다.

다음으로 재귀 케이스이다. blankPositions[blankIndex]로 현재 조사할 빈칸 좌표를 받아온 뒤, 이 좌표에 대해 getPossibleNumbers()을 수행하여, 삽입할 숫자 후보들을 가져온다. 숫자 후보들(possibleNumbers)을 for문으로 돌면서 백트래킹 작업을 수행해준다. 이 때, 스도쿠가 정답이어서 True를 반환했으면, 이후에는 출력을 하면 안 되므로 곧바로 재귀를 탈출해준다.