[Python] Baekjoon - 2239. 스도쿠

백준 2239번 스도쿠 문제는 일반적인 스도쿠 문제를 백트래킹 기법을 사용하여 해결하는 문제다. 빈칸이 있는 9칸 스도쿠 퍼즐이 주어졌을 때 빈칸을 모두 채워서 출력하는 문제이며 사전 순으로 가장 빠른 답을 출력해야 한다. 난이도는 골드 4이다.

 

백준 2239번 스도쿠 문제 정보

알고리즘 분류

- 백트래킹

난이도

- 골드 4

스도쿠 문제 요약

• 9x9 크기의 스도쿠에 빈칸들이 주어졌을 때, 빈칸을 모두 채워서 출력하는 문제다.
• 사전 순으로 가장 빠른 답을 출력한다.

문제 풀이 방법 1 (일반적인 방식)

과정

• 스도쿠 보드판을 입력받을 때 빈칸들의 좌표를 따로 저장해둔다.
• 모든 빈칸들에 대해서 백트래킹 수행한다.
• 각 빈칸에서 넣을 수 있는 숫자들을 구해서 해당 숫자들 넣고 다음 depth로 진행한다.
• 넣을 수 있는 숫자가 없는 경우 백 트래킹 한다.
• Python3로 제출할 경우 시간 초과가 나고 PyPy3로 제출하면 통과가 가능하다.

코드 설명

• getPromising(r,c): (r,c)칸에 넣을 수 있는 숫자를 구하는 함수
  • [True] * 10으로 1~9 각각이 들어갈 수 있는지 표시하는 배열 생성
  • r행, c열, (r,c)가 포함된 작은 정사각형 칸에 등장하는 숫자는 배열에서 False로 바꾸기
  • 체크 후 여전히 True인 인덱스들 반환
• backtracking(depth): depth번째 빈칸에 숫자를 넣을 수 있으면 넣고 계속 진행, 넣을 수 없으면 되돌아가는 재귀 함수
  • 빈칸을 모두 채우면 스도쿠판 출력하고 종료

def getPromisingNums(r, c):
    global board
    res = [False] + [True for _ in range(9)]

    for k in range(9):
        res[int(board[r][k])] = False
        res[int(board[k][c])] = False

    for i in range(3*(r//3),3*(r//3)+3):
        for j in range(3*(c//3),3*(c//3)+3):
            res[int(board[i][j])] = False

    return [str(idx) for idx, _ in enumerate(res) if _]


def backtracking(depth):
    global board, blanks, isEnd

    if isEnd:
        return

    if depth == len(blanks):
        isEnd = True
        for x in board:
            print(''.join(x))
        return

    r, c = blanks[depth]
    for n in getPromisingNums(r, c):
        board[r][c] = n
        backtracking(depth+1)
    board[r][c] = '0'


if __name__ == '__main__':
    board = []
    blanks = []
    isEnd = False

    for i in range(9):
        tmp = list(input())
        board.append(tmp)
        for j in range(9):
            if tmp[j] == '0':
                blanks.append((i,j))

    backtracking(0)

 

문제 풀이 방법 2 (Python3로 통과 가능한 방식)

과정

• 각 빈칸에 넣을 수 있는 숫자들을 구하는 함수를 간소화하여 속도를 줄였다.

코드 설명

• boardRow, boardCol, boardSquare: 각 행, 각 열, 각 정사각형에 들어갈 수 있는 숫자를 표시하는 배열
  • 각 빈칸에서 위의 배열의 값이 모두 True인 숫자만 넣을 수 있다.

def getPromisingNums(r, c):
    global boardRow, boardCol, boardSquare
    return [n for n in range(1, 10) if boardRow[r][n] and boardCol[c][n] and boardSquare[(r//3)*3 + (c//3)][n]]


def backtracking(depth):
    global board, blanks, isEnd, boardRow, boardCol, boardSquare

    if isEnd:
        return

    if depth == len(blanks):
        isEnd = True
        for row in board:
            for x in row:
                print(x, end='')
            print()
        return

    r, c = blanks[depth]
    for n in getPromisingNums(r, c):
        boardRow[r][n] = False
        boardCol[c][n] = False
        boardSquare[(r//3)*3 + (c//3)][n] = False
        board[r][c] = n
        backtracking(depth+1)
        boardRow[r][n] = True
        boardCol[c][n] = True
        boardSquare[(r//3)*3 + (c//3)][n] = True
        board[r][c] = 0


if __name__ == '__main__':
    board = []
    blanks = []
    isEnd = False

    boardRow, boardCol, boardSquare = [[True] * 10 for _ in range(9)], [[True] * 10 for _ in range(9)], [[True] * 10 for _ in range(9)]

    for i in range(9):
        tmp = list(map(int, list(input())))
        board.append(tmp)
        for j in range(9):
            here = tmp[j]
            if here == 0:
                blanks.append((i,j))
            else:
                boardRow[i][here] = False
                boardCol[j][here] = False
                boardSquare[(i//3)*3 + (j//3)][here] = False

    backtracking(0)