(Python) 백준 2239

백준 2239

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	21112	10227	7334	46.045%

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++17: 180ms
  • Java 15: 528ms
  • PyPy3: 2064ms

---

답안

import sys

class Board:
    board = []
    rows = []
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty_cells = []
    _presence = [False] * 10

    def __init__(self):
        for i in range(9):
            line = list(map(int, list(sys.stdin.readline().rstrip())))
            for j in range(9):
                if line[j] == 0:
                    self.empty_cells.append((i, j))
            self.rows.append(set(line) - {0})
            self.board.append(line)
        for i in range(9):
            for j in range(9):
                if self.board[i][j] == 0:
                    continue
                self.cols[j].add(self.board[i][j])
                self.boxes[i//3*3 + j//3].add(self.board[i][j])

    def place(self, row, col, value):
        self.board[row][col] = value
        self.rows[row].add(value)
        self.cols[col].add(value)
        self.boxes[row//3*3 + col//3].add(value)

    def unplace(self, row, col, value):
        self.board[row][col] = 0
        self.rows[row].remove(value)
        self.cols[col].remove(value)
        self.boxes[row//3*3 + col//3].remove(value)

    def print(self):
        for i in range(9):
            for j in range(9):
                print(self.board[i][j], end='')
            print()

def solve(board, start=0):
    if start >= len(board.empty_cells):
        board.print()
        exit()

    row, col = board.empty_cells[start]
    for i in set([i for i in range(1, 10)]) - (board.rows[row] | board.cols[col] | board.boxes[row//3*3 + col//3]):
        board.place(row, col, i)
        solve(board, start+1)
        board.unplace(row, col, i)

board = Board()
solve(board)

주의: 이 코드는 Python3로 채점하면 시간초과 판정을 받습니다. PyPy3로 채점받아야 정답 판정을 받게 됩니다.

풀이

백트래킹을 이용해서 풀었다.

처음의 빈칸에 1~9까지 넣어보다가, 그 중 어떤 수가 가능하면 다음 빈칸에 1~9까지 넣어보다가, … 만약 1~9까지의 모든 수가 불가능하다면 그 전 단계로 돌아가는 것을 반복한다.

def solve(board, start=0):
    if start >= len(board.empty_cells):
        board.print()
        exit()

    row, col = board.empty_cells[start]
    for i in set([i for i in range(1, 10)]) - (board.rows[row] | board.cols[col] | board.boxes[row//3*3 + col//3]):
        board.place(row, col, i)
        solve(board, start+1)
        board.unplace(row, col, i)

그런데 이렇게 하려면 그 전 단계의 스도쿠 판의 상태와 지금까지 어떤 칸에 어떤 숫자를 두었다는 기록들이 남아있어야 하는데, 그것을 모든 단계에 대해 기록하게 되면 시간, 메모리 두 측면에서 아주 많은 리소스를 낭비하게 된다.

따라서 스도쿠 판에 어떤 숫자를 두었을 때, 만약 그 숫자를 넣었을 때 스도쿠가 풀리지 않는다면 board.unplace()를 통해 스도쿠 판에서 해당 숫자를 지우게 하였고, 지금까지 어떤 칸에 어떤 숫자를 두었는지는 재귀를 통해 stack에 저장되었다.

처음에는 아래와 같이 set이 아닌 list로 풀었다. 이렇게 하더라도 정답 판정은 받으나, 조금의 변경만 가해도 시간 초과 판정을 받을만큼 시간이 아주 많이 걸렸다.

import sys

class Board:
    rows = []
    cols = [[0]*9 for _ in range(9)]
    boxes = [[] for _ in range(9)]
    empty_cells = []
    _presence = [False] * 10

    def __init__(self):
        for i in range(9):
            line = list(map(int, list(sys.stdin.readline().rstrip())))
            for j in range(9):
                if line[j] == 0:
                    self.empty_cells.append((i, j))
            self.rows.append(line)
        for i in range(9):
            for j in range(9):
                self.cols[j][i] = self.rows[i][j]
                self.boxes[i//3*3 + j//3].append(self.rows[i][j])

    def place(self, row, col, value):
        self.rows[row][col] = value
        self.cols[col][row] = value
        self.boxes[row//3*3 + col//3][row % 3 * 3 + col % 3] = value

    def unplace(self, row, col):
        self.rows[row][col] = 0
        self.cols[col][row] = 0
        self.boxes[row//3*3 + col//3][row % 3 * 3 + col % 3] = 0

    def print(self):
        for i in range(9):
            for j in range(9):
                print(self.rows[i][j], end='')
            print()

    def is_valid(self, row, col):
        return self._is_row_valid(row) and self._is_col_valid(col) and self._is_box_valid(row//3*3 + col//3)

    def _is_row_valid(self, row_number):
        return self._is_not_duplicated(self.rows, row_number)

    def _is_col_valid(self, col_number):
        return self._is_not_duplicated(self.cols, col_number)

    def _is_box_valid(self, box_number):
        return self._is_not_duplicated(self.boxes, box_number)

    def _is_not_duplicated(self, target_list, number_order):
        for i in range(10):
            self._presence[i] = False
        for i in range(9):
            element = target_list[number_order][i]
            if element == 0:
                continue
            if self._presence[element] == True:
                return False
            self._presence[element] = True
        return True

def solve(board, start=0):
    if start >= len(board.empty_cells):
        board.print()
        exit()

    row, col = board.empty_cells[start]
    for i in range(1, 10):
        board.place(row, col, i)
        if board.is_valid(row, col):
            solve(board, start+1)
        board.unplace(row, col)

board = Board()
solve(board)

다른 풀이들을 보고 어떻게 이것을 개선할 수 있을지 고민해본 결과, set으로 바꿨더니 실행 시간이 1/2배로 감소하는 것을 확인할 수 있었다.

스도쿠 판에 이 숫자를 넣어도 괜찮은지 validity를 확인하는 과정에서 아주 많은 시간을 사용했던 것으로 추정되는데, set을 이용한 구현에서는 집어넣을 수 있는 숫자를 합집합(|)과 차집합(-) 연산자를 통해 바로 구할 수 있으니 시간이 단축되었던 것 같다.

구현이 단순해져 보기 좋아진 것도 아주 좋다.

다음에는 어디에 포함되어 있는지 확인할 때 리스트를 순회하기보다 set을 사용하는 것을 고려해봐야겠다.