[백준] 스도쿠(2239) - python

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

 

문제 요약

스도쿠판이 주어졌을 때 스도쿠 판을 채우는 문제입니다. 문제 조건에 동일한 정답이 있을 경우 81자리가 가장 작은 숫자를 답으로 설정하라는 조건이 있습니다.

 

풀이 방식

먼저 백트래킹을 사용해서 구현을 진행하였습니다. 먼저 2차원 배열에 입력을 받아서 앞에서부터 빈칸을 채우면서 백트래킹을 진행하는 방식으로 설계하여 구현했습니다. 따라서 아래 코드가 정답으로 나왔는데 아래 코드는 pypy3을 사용해서 정답으로 통과가 되었고 python3에서는 시간 초과가 되었습니다.

 

정답 코드

import sys
input = sys.stdin.readline

class Sudoku:
    def __init__(self):
        self.board = [list(map(int, list(input().strip()))) for _ in range(9)]
    
    def possibleNumber(self, x, y, num):
        for i in range(9):
            if self.board[x][i] == num or self.board[i][y] == num:
                return False
        x //= 3
        y //= 3
        for i in range(x * 3, (x + 1) * 3):
            for j in range(y * 3, (y + 1) * 3):
                if self.board[i][j] == num:
                    return False
        return True
    
    def backtracking(self):
        empty_cells = [(i, j) for i in range(9) for j in range(9) if self.board[i][j] == 0]

        index = 0
        while index < len(empty_cells):
            x, y = empty_cells[index]
            found = False

            for num in range(self.board[x][y] + 1, 10):
                if self.possibleNumber(x, y, num):
                    self.board[x][y] = num
                    index += 1
                    found = True
                    break
            
            if not found:
                self.board[x][y] = 0
                index -= 1
    
    def printBoard(self):
        for i in range(9):
            print(*self.board[i],sep='')

def main():
    sudoku = Sudoku()
    sudoku.backtracking()
    sudoku.printBoard()

if __name__ == "__main__":
	main()

 

 

문제점 및 개선 사항

python3에서 통과하는 방식을 생각하면서 여러 정보를 찾아보았습니다. 가장 큰 문제는 빈칸에 가능한 숫자를 비교하고 값을 넣고 삭제하는 연산이 오래걸린다는 것을 알게 되었습니다. 따라서 더 나은 방법인 비트마스크를 이용한 방법을 알게 되었습니다. 이 방법은 비트연산자를 통해 각 칸에 해당하는 값을 비트로 표현하는 방식입니다. 먼저 열, 행, 박스별 비트 마스크를 설정해 주고 연산을 비트 마스크를 통해 진행해 줍니다.

class Sudoku:
    def __init__(self, board):
        self.board = board
        self.row = [0] * 9  # 각 행에 숫자의 존재 상태를 비트마스크로 저장
        self.col = [0] * 9  # 각 열에 숫자의 존재 상태를 비트마스크로 저장
        self.box = [0] * 9  # 각 박스에 숫자의 존재 상태를 비트마스크로 저장
        self.empty_cells = []  # 빈 칸
        self.init_state()

    def init_state(self):
        for i in range(9):
            for j in range(9):
                if self.board[i][j] == 0:
                    self.empty_cells.append((i, j))
                else:
                    num = self.board[i][j]
                    self.set_bit(i, j, num, True)

    def set_bit(self, x, y, num, state):
        mask = 1 << (num - 1)
        self.row[x] = self.row[x] | mask if state else self.row[x] & ~mask
        self.col[y] = self.col[y] | mask if state else self.col[y] & ~mask
        box_index = (x // 3) * 3 + (y // 3)
        self.box[box_index] = self.box[box_index] | mask if state else self.box[box_index] & ~mask

    def is_valid(self, x, y, num):
        mask = 1 << (num - 1)
        box_index = (x // 3) * 3 + (y // 3)
        return not (self.row[x] & mask or self.col[y] & mask or self.box[box_index] & mask)
    
    def solve(self, index=0):
        if index == len(self.empty_cells):
            return True

        x, y = self.empty_cells[index]
        for num in range(1, 10):
            if self.is_valid(x, y, num):
                self.board[x][y] = num
                self.set_bit(x, y, num, True)

                if self.solve(index + 1):
                    return True

                self.board[x][y] = 0
                self.set_bit(x, y, num, False)
        return False

    def print_board(self):
        for row in self.board:
            print("".join(map(str, row)))

가장 중요한 변경사항은 빈칸에 들어가는 값의 비교를 비트 연산을 통해 진행했다는 점입니다. 이때의 장점으로 한 정수 안에 숫자들의 상태를 모두 표현할 수 있고 메모리 사용이 적고 접근 및 수정이 빠르다는 점이 있습니다. 그러나 이렇게 수정을 진행해도 python3에서는 시간초과가 나왔지만 pypy3에서는 시간을 많이 줄일 수 있었습니다.