[백준알고리즘] 2580번: 스도쿠 -Python

[백준알고리즘] 2580번: 스도쿠 -Python

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

2580번: 스도쿠

2020.03.11 거의 유사하긴 하나, 새로 푼 코드를 아래에 추가했다.

---

와 이거 푸는데 되게 오래 걸렸다... 처음에 C로 하려고 까불다가 머리 깨질뻔하고 파이썬으로 넘어와서 하다가... 파이썬으로도 다르게 풀어보면서 이래저래 하다가 겨우 풀었다... 다 풀고 보니까 왜 이걸 이렇게 끌었나 싶당. 4, 5번은 갈아엎은 것 같은데..ㅜㅜ

 

C로 하다가 포기한건 C++의 <vector>나 이런 것들을 안 쓰고 하다가 너무 오래 걸릴 것 같아서 파이썬으로 갈아탔다. C로 한 사람들이 있나 구글링 해보는데 내가 본 것들은 다 C++이었다. C로 짠 코드 한 번 보고 싶다!

 

파이썬으로 풀 때는 채울 빈칸들을 row단위로 처리를 하려 했다. 그러다 보니 row의 빈칸에 들어갈 수 있는 순서쌍들(순열)의 수가 많았고, 해당 순서쌍이 row의 빈칸에 들어갈 수 있는지 확인하는 과정에서 중복해서 비교하는 시간들이 많이 끼게 되었다. 예를 들어 하나의 row에 빈칸이 3개이고 필요한 숫자들이 (1, 2, 3)이라고 하자. (1, 2, 3)이 들어갈 수 있는지 확인하기 위해서 1, 2, 3을 세 개의 빈칸에 순서대로 모두 검사를 수행했더니 들어갈 수 없는 순서쌍으로 나왔다. 그렇다면 (1, 3, 2)를 검사하는데 여기서 1은 이전에 처리했던 검사를 한 번 더 수행하게 되는 것이다.

 

이것을 깨닫고 난 이후에는 빈 칸별로 하나씩 처리를 해주었다. 이것도..... 시간이 되게 오래 걸린다. Python3로는 시간 초과가 발생하고 Pypy3로 통과했다. 아마 각 빈칸당 들어갈 수 있는 수들의 리스트를 만들 때가 오래 걸리는 것 같은데, in으로 검사하고 remove로 지우는 과정 대신에 boolean list를 만들어 체크해서 기존에 없는 숫자들만 뽑는 게 조금 더 빠를 것 같다. 하지만 거기까지는.. ㅎ.. 해보지 않을 예정이다...

 

아무튼 이것저것 삽질하다가 시간이 오래 잡혔고, Python3로는 통과한 사람이 별로 없는 것 같으니 Pypy3로 해보는 걸 추천한다. 그리고 아래는 추가적으로 찾은 예시들이다. 특히 첫 번째 예시는 시간이 되게 오래 걸린다. 이게 금방 뜨면 되게 잘 짠 코드일 텐데..

 

#case1

0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9

 

#case2

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 3 0
0 0 0 0 0 0 0 0 0
0 0 0 4 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

아래는 코드다.

import sys

sudoku = []
zero = []
S_SIZE = 9
Z_SIZE = 0
END_FLAG = False

for i in range(S_SIZE):
    sudoku.append(sys.stdin.readline().split())
    for j in range(S_SIZE):
        if sudoku[i][j] == '0':
            zero.append([i, j])
            Z_SIZE += 1

def get_possible(zero):
    a, b = zero
    nums = list(map(str, range(1, 10)))

    for i in range(S_SIZE):
        if sudoku[a][i] in nums:
            nums.remove(sudoku[a][i])
        if sudoku[i][b] in nums:
            nums.remove(sudoku[i][b])

    if len(nums) > 0:
        rt = (a // 3) * 3
        ct = (b // 3) * 3

        for i in range(rt, rt+3):
            for j in range(ct, ct+3):
                if sudoku[i][j] in nums:
                    nums.remove(sudoku[i][j])
    return nums


def solve(idx):
    if idx == Z_SIZE:
        global END_FLAG
        END_FLAG = True
        return

    global sudoku    
    a, b = zero[idx]
    possible = get_possible(zero[idx])

    for p in possible:
        sudoku[a][b] = p
        solve(idx+1)
        if END_FLAG:
            return
    
    if END_FLAG == False:
        sudoku[a][b] = '0'


solve(0)

for s in sudoku:
    sys.stdout.write(' '.join(s))
    sys.stdout.write('\n')

 

2020.03.11

새로 풀었는데 이전 방식과 비슷한 것 같다.

 

set을 이용한다는 점만 다른 것 같다.

 

Python으로 통과한 코드들을 확인해봤는데 각 열, 행, 3x3크기의 박스에서 가능한 수들을 계속 유지하고, (i, j)를 (0, 0)부터 (8, 8)까지 가면서 모두 확인을 하는 코드였다. 확인 후 1~9 중에서 열, 행, 박스에 모두 존재하는 수들만 넣어보고 다음으로 진행하도록 했다. 그리고 마지막 번호까지 도착하면 출력 후 exit()으로 바로 빠져나왔다.

 

이 방식은 나중에 풀 때 해보도록 해야겠다.

 

import sys
sys.setrecursionlimit(10**9)

def get_possible(i, j):
    num = set('123456789')
    row = set(table[i])
    col = set([table[t][j] for t in range(9)])
    box = set([table[p][q] for p in range(3*(i//3), 3*(i//3) + 3) for q in range(3*(j//3), 3*(j//3) + 3)])

    num = num.difference(row)
    num = num.difference(col)
    num = num.difference(box)

    return num

def solve(idx):
    if idx == len_zero:
        return True
    
    i, j = zero[idx]
    vset = get_possible(i, j)
    for v in vset:
        table[i][j] = v
        if solve(idx+1):
            return True
        else:
            table[i][j] = '0'
    return False

table = [list(sys.stdin.readline().split()) for _ in range(9)]
zero = []
for i in range(9):
    for j in range(9):
        if table[i][j] == '0':
            zero.append((i, j))

len_zero = len(zero)
if len_zero > 0:
    solve(0)

for t in table:
    print(' '.join(t))

 

2020.04.04

새로 풀었는데 이전보다 속도가 반정도로 줄었다.

하지만 여전히 PyPy로만 통과한 코드이며, Python으로는 80퍼센트 대에서 시간초과가 발생한다.

 

게시판을 보니 각 지점마다 가능한 번호들을 매번 계산하기 때문에 시간이 오래 걸린다는 것 같다.

그래도 지금은 반정도 줄인 것에 만족해야겠다. 0인 지점을 볼 때마다 해당 좌표가 포함된 열, 행, 3x3박스를 모두 확인했었는데, 이 부분을 초반에 각 행, 열, 박스마다 가능한 수를 미리 다 구해놨었기 때문에 중복해서 구하는 일을 제거했다.

 

처음에 PyPy로 제출했을 때 계속 런타임 에러가 났었는데 exit() 때문이었다.

이 부분도 게시판을 보고 알았는데 PyPy를 사용하면 sys.exit()을 사용해주어야 한다. 이 부분을 고치고나서 통과했다.

from sys import exit

def dfs(idx):
    if idx == len_z:
        for i in range(9):
            for j in range(9):
                print(table[i][j], end=" ")
            print()
        exit()

    i, j = zero[idx]
    box_idx = 3*(i//3)+j//3
    possible = prows[i].intersection(pcols[j].intersection(pbox[box_idx]))
    for p in possible:
        prows[i].discard(p)
        pcols[j].discard(p)
        pbox[box_idx].discard(p)
        table[i][j] = p
        dfs(idx+1)
        prows[i].add(p)
        pcols[j].add(p)
        pbox[box_idx].add(p)

table = [list(map(int, input().split())) for _ in range(9)]
nums = set(range(1, 10))
prows = [nums - set(table[i]) for i in range(9)]
pcols = [nums - set(table[i][j] for i in range(9)) for j in range(9)]
pbox = [nums - set(table[i][j] for i in range(p, p+3) for j in range(q, q+3))\
    for p in range(0, 9, 3) for q in range(0, 9, 3)]

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

len_z = len(zero)
dfs(0)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다