백준 2580번 문제 - 스도쿠 (나의 파이썬 풀이과정)

금요일부터 풀기시작한 문제를 방금 끝냈다

 

이번 포스팅에서부터는 그냥 풀이과정이란말을 나의 풀이과정으로 바꿀생각이다

솔직히 검색하시는분은 아마 정답을 보고싶어서 검색하실텐데 그냥 풀이과정이라고 써놓으면

오해를 살것같아서 말이다

 

n-queen과 정말 유사한 문제라 빨리풀거라고 생각했는데 생각보다 오래걸린것같다

역시 난 똑똑한 편은 아닌걸로...

 

n-queen에서 시간초과가 났던 그방법 그대로를 재현해서 도전하였다 ㅋㅋ

이번엔 다르겠지 이생각이었었던것같다

 a=list(map(int,input().strip().split()))
board=[ a[i*9:(i+1)*9]   for i in range(9)]
printed=0
x=set([1,2,3,4,5,6,7,8,9])
# import numpy as np
import copy
def sudoku(board):
    global printed # 하나의 결과물만 출력하기위해
    if printed>0: # 이미 결과물이 나왔으면 빠르게 return
        return
    hole=0
    # 보드 생성
    for row in range(9): # 행탐색
        if hole > 0:
            break # 빈칸을 하나라도 탐색했다면 break 재귀된 함수와 겹치지않기위해
        for column in range(9): # 열탐색
            # 들어갈수있는 수 검사하기
            if board[row][column] == 0: # 빈칸이있다면
                hole+=1
                # 행의 빈칸
                r=list(x-set(board[row]))
                # 열의 빈칸
                c=list(x-set([board[i][column] for i in range(9)]))
                # 박스의 빈칸
                m=[i[column//3*3:column//3*3+3] for i in board[row//3*3:row//3*3+3]]
                box=[]
                for i in m:
                    for j in i:
                        box.append(j)
                b=list(x-set(box))
                # 만약 빈칸에 들어갈 경우의 수가 있다면?
                if len(list(set(r)&set(c)&set(b))) > 0:
                    
                    # 경우의 수만큼의 새로운 브랜치(재귀)
                    for i in list(set(r)&set(c)&set(b)):
                        new_board=copy.deepcopy(board)
                        new_board[row][column]=i
                        sudoku(new_board)
                break                
            
    if hole==0:
        if printed==0:
            for i in board:
                for j in i:
                    print(j, end=' ')
            # print(np.reshape(board,(9,9)))
            printed+=1
       
sudoku(board)

틀렸습니다, 시간초과도 아닌 index 에러가 나서 이것때문에 시간을 꽤 소비했다

왜냐면 아무리 봐도 index에러가 날수 없었던 구조였기때문이었다

결국 동료의 도움으로 원인을 찾아냈는데 

여러줄을 입력으로 받아야되는데 내가 한줄에 모든 입력을 받는것으로 착각했기때문이었다

그래서 고쳐서 다시냈다

import sys
input=sys.stdin.readline
board=[list(map(int,input().split())) for i in range(9)]
printed=0
x=set([1,2,3,4,5,6,7,8,9])
# import numpy as np
import copy
def sudoku(board):
    global printed # 하나의 결과물만 출력하기위해
    if printed>0: # 이미 결과물이 나왔으면 빠르게 return
        return
    hole=0
    # 보드 생성
    for row in range(9): # 행탐색
        if hole > 0:
            break # 빈칸을 하나라도 탐색했다면 break 재귀된 함수와 겹치지않기위해
        for column in range(9): # 열탐색
            # 들어갈수있는 수 검사하기
            if board[row][column] == 0: # 빈칸이있다면
                hole+=1
                # 행의 빈칸
                r=list(x-set(board[row]))
                # 열의 빈칸
                c=list(x-set([board[i][column] for i in range(9)]))
                # 박스의 빈칸
                m=[i[column//3*3:column//3*3+3] for i in board[row//3*3:row//3*3+3]]
                box=[]
                for i in m:
                    for j in i:
                        box.append(j)
                b=list(x-set(box))
                # 만약 빈칸에 들어갈 경우의 수가 있다면?
                if len(list(set(r)&set(c)&set(b))) > 0:
                    
                    # 경우의 수만큼의 새로운 브랜치(재귀)
                    for i in list(set(r)&set(c)&set(b)):
                        new_board=copy.deepcopy(board)
                        new_board[row][column]=i
                        sudoku(new_board)
                break                
            
    if hole==0:
        if printed==0:
            for i in board:
                print(*i)
                # for j in i:
                #     print(j, end=' ')
            # print(np.reshape(board,(9,9)))
            printed+=1
       
sudoku(board)

역시 시간초과였다

여기서 인터넷에서 답을 검색해 보았다

import sys
input=sys.stdin.readline
board=[list(map(int,input().split())) for i in range(9)]
printed=0
x=set([1,2,3,4,5,6,7,8,9])
import copy

hole=[]
for row in range(9):
    for col in range(9):
        if board[row][col]==0:
            hole.append( (row,col) )



def sudoku(board,idx):
    # global printed # 하나의 결과물만 출력하기위해
    if idx==len(hole): # 이미 결과물이 나왔으면 빠르게 return
        for i in board:
            print(*i)
        exit(0)
                
    row=hole[idx][0]
    column=hole[idx][1]
    # 행의 빈칸
    r=list(x-set(board[row]))
    # 열의 빈칸
    c=list(x-set([board[i][column] for i in range(9)]))
    # 박스의 빈칸
    m=[i[column//3*3:column//3*3+3] for i in board[row//3*3:row//3*3+3]]
    box=[]
    for i in m:
        for j in i:
            box.append(j)
    b=list(x-set(box))
    # 만약 빈칸에 들어갈 경우의 수가 있다면?
    if len(list(set(r)&set(c)&set(b))) > 0:
    # 경우의 수만큼의 새로운 브랜치(재귀)
        for i in list(set(r)&set(c)&set(b)):
            new_board=copy.deepcopy(board)
            new_board[row][column]=i
            sudoku(new_board, idx+1)
                      
sudoku(board,0)

원래같은경우에서는 빈곳은 찾을때 함수가 시작할때마다 탐색했는데 

구멍뚫린곳을 처음에 미리 탐색해서

함수가 돌아갈때마다 반복적으로 빈곳을 찾는 비효율을 개선했다

하지만 이번에도 시간초과

 

내가 사용하는 판 물려주기방식에대한 못미더움이 생기기시작했다

 

알고보니 set 연산이 각각 엄청나게 시간복잡도를 소모했다 각각 2n씩이다

(s - t 기준 O(len(s)+len(t))인데 2n으로 봐도 될것같았다)

또 copy 할때마다 n의 시간복잡도를 가진다

 

또한 빈칸 한군데의 경우의 수에따라 그만큼의 복제 스도쿠 판이 생성되는건 덤이다

 

따라서 빈칸 한군데를 체크할때마다 시간복잡도는 대략

11n+n**2가 나오는것같다

 

한번 copy할때마다 시간복잡도가 생긴다는사실을 왜 몰랐을까 

다시한번 검색을 해봤고 완전히 이해를 한뒤에 스스로 코드를 짜봤다

참고한곳(아래)

[백준] 2580 스도쿠 (Python 파이썬) :: AndroidTeacher (tistory.com)

import sys
input=sys.stdin.readline
board=[list(map(int,input().split())) for i in range(9)]
hole=[]
for row in range(9):
    for col in range(9):
        if board[row][col]==0:
            hole.append( (row,col) )

def row_check(row,num):
    for i in range(9):
        if board[row][i] == num:
            return True
    return False

def col_check(col,num):
    for i in range(9):
        if board[i][col] == num:
            return True
    return False

def box_check(row, col, num):
    for i in range(row//3*3,row//3*3+3):
        for j in range(col//3*3,col//3*3+3):
            if board[i][j] == num:
                return True
    return False


def sudoku(idx):
    if idx==len(hole):
        for i in board:
            print(*i)
        exit(0)
    
    
    row=hole[idx][0]
    col=hole[idx][1]
    num=board[row][col]
    for i in range(1, 10):
        if row_check(row,i):
            continue
        if col_check(col,i):
            continue
        if box_check(row,col,i):
            continue
        board[row][col]=i
        sudoku(idx+1)
        board[row][col]=0


        
if len(hole)==0:
    for i in board:
        print(*i)
else:
    sudoku(0)

n-queen때는 코드 이해만 후 제출한뒤 넘어갔는데 이번엔 한번보고 나스스로 코드를 다시 쳐보았다

continue를 이용해서 3조건중 하나만 틀려도 바로 다음 반복문으로 넘어갈수있게끔하였다

 

총 시간복잡도는 2n+n**2 정도인것같다

게다가 continue덕분에 최대시간복잡도와 실제 시간복잡도의 차이가 있을것이다

 

확실히 내가 스스로 구현한 코드보다 빠르다는 사실을 알수있었다

 

그나저나 이게 원본 그대로 제출했을때보다 느리길래 (pypy기준 원본에서는 and연산자를 썻다)

and연산자 사용해서 다시 내보았는데 continue썻을때보다 느렸다(당연하게도)

왜 그분보다 느린진 알수없었지만 어쨋든 and보다 continue사용했을때 더빠른것은 입증되었다

 

이상한게 그냥 일반변수는 함수안에서 영향을 줄수없었는데 

리스트는 영향을 주는게 가능하다는 사실을 이번에 알게되었다

빈칸인부분에대해서 1에서9의 숫자를 대입해

열, 행, 그리고 박스(3*3부분)에대하여 모두 테스트를 통과하는경우 

더깊은 트리를 생성한다

 

대입되는 숫자중에 조건을 불만족하는경우 바로 return되고 

3조건중 하나라도 만족하지못하는경우 바로 다음 반복문으로 넘어가기때문에

최대 시간복잡도와 실제 시간복잡도는 차이가 있을것이다

 

다음 board를 물려주는 방식대신 그냥 간단하게

테스트를 통과한 수를 board에 대입시키고 재귀시키는것으로 구현되었다

생각해보니 재귀가 일어나면 부모 함수의 동작이 정지되고 재귀 함수가 우선적으로 처리되기에 문제가 없었다

 

이번에는 N-Queen처럼 경우의 수만 출력하는것이 아닌 보드 전체를 출력하는것이라서

무조건 이번에는 copy를써서 보드를 물려주는식으로 진행해야된다고 생각했었는데 아니었던것이었다

 

copy하는데 쓰이는 시간복잡도와 메모리를 아낄수있었다

 

만약 해당 브랜치에서 빈칸에 들어갈수있는 수가없어 또다른 재귀가 일어나지 않았을경우 다시

board[row][col]=0가 실행되면서 초기화가 되고 다음 수를 대입할수있게된다

 

그리고 if idx==len(hole)을 만족시키게되면 보드를 출력한뒤 

exit(0)으로 끝낸다

exit은 이번에 처음본 친군데

코랩기준으로 그냥 런타임을 끝내버린다(알수없는이유로 세션이 종료되었다고 뜬다)

프로그램 자체를 종료시킨다 마치 코드를 뽑는것처럼 

 

출력값이 나오자마자 exit(0)으로 나오면서 극한의 효율을 추구한다 

이렇게 제출해서 통과할수있었고 자기전에 끝냈음에 안도의 한숨을 내쉬었다

 

다만 프로그램을 강제로 종료시키는것에대해 좋은방법은 아니라고 생각해서 exit를 이용하지않고 구현해보았다

# import sys
# input=sys.stdin.readline
# board=[list(map(int,input().split())) for i in range(9)]
board=[[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, 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, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0]]
printed=0
hole=[]
for row in range(9):
    for col in range(9):
        if board[row][col]==0:
            hole.append( (row,col) )

def row_check(row,num):
    for i in range(9):
        if board[row][i] == num:
            return True
    return False

def col_check(col,num):
    for i in range(9):
        if board[i][col] == num:
            return True
    return False

def box_check(row, col, num):
    for i in range(row//3*3,row//3*3+3):
        for j in range(col//3*3,col//3*3+3):
            if board[i][j] == num:
                return True
    return False


def sudoku(idx):
    global printed
    if printed>0:
        return
    
    
    
    if idx==len(hole):
        if printed == 0:
            for i in board:
                print(*i)
            printed+=1 
        return
    
    row=hole[idx][0]
    col=hole[idx][1]
    num=board[row][col]
    for i in range(1, 10):
        if row_check(row,i):
            continue
        if col_check(col,i):
            continue
        if box_check(row,col,i):
            continue
        board[row][col]=i
        sudoku(idx+1)
        board[row][col]=0


if len(hole)==0:
    for i in board:
        print(*i)
else:
    sudoku(0)

최초로 나온 출력값을 출력후 return

그후 나머지 함수들은 맨위에서 return 시켜서 전체 프로그램을 종료시켰다

 

이렇게해서 문제풀이는 끝나고 번외로 

저번에 N-Queen에서 했던것처럼 이번엔 스도쿠  푸는 기계를 만들어보았다

def row_check(row,num):
    for i in range(9):
        if board[row][i] == num:
            return True
    return False

def col_check(col,num):
    for i in range(9):
        if board[i][col] == num:
            return True
    return False

def box_check(row, col, num):
    for i in range(row//3*3,row//3*3+3):
        for j in range(col//3*3,col//3*3+3):
            if board[i][j] == num:
                return True
    return False


def solve(idx):
    global count
    if idx==len(hole):
        print(count)
        print('-'*20)
        for i in board:
            print(*i)
        print('-'*20)
        count+=1       
        return
        
    row=hole[idx][0]
    col=hole[idx][1]
    num=board[row][col]
    for i in range(1, 10):
        if row_check(row,i):
            continue
        if col_check(col,i):
            continue
        if box_check(row,col,i):
            continue
        board[row][col]=i
        solve(idx+1)
        board[row][col]=0

def is_row_possible(board):
    new_board=copy.deepcopy(board)
    for i in new_board:
        while 0 in i:
            i.remove(0)
        if len(i)!=len(set(i)):
            return False
    return True


def is_col_possible(board):
    new_board=copy.deepcopy(board)
    for i in range(9):
        test=[]
        for j in range(9):
            test.append(new_board[j][i])
        while 0 in test:
            test.remove(0)
        if len(test)!=len(set(test)):
            return False
    return True

def is_box_possible(board):
    new_board=copy.deepcopy(board)
    for i in [0,3,6]:
        for j in [0,3,6]:
            test1=[]
            for k in range(i//3*3,i//3*3+3):
                for p in range(j//3*3,j//3*3+3):
                    test1.append(new_board[k][p])
            while 0 in test1:
                test1.remove(0)
            if len(test1)!=len(set(test1)):
                return False
    return True
    

def sudoku():
    if len(hole)==0:
        print('-'*20)
        print('이미 완성된 퍼즐입니다')
    else:
        if is_row_possible(board) and is_col_possible(board) and is_box_possible(board):
            solve(0)
            print(f'입력하신 퍼즐을 채울수있는 경우의 수는 {count-1}가지 입니다')
        else:
            print('-'*20)
            print('맞출 수 없는 퍼즐입니다')

# 9*9 스도쿠 퍼즐을 한줄씩 입력해주세요 총 9번 입력받습니다, 9개의 숫자들을 한칸씩 공백을 두고 입력해주세요
# 빈칸은 0으로 표시해주세요 
import copy
board=[list(map(int,input().split())) for i in range(9)]
count=1
hole=[]
for row in range(9):
    for col in range(9):
        if board[row][col]==0:
            hole.append( (row,col) )
sudoku()

ㅎㅎ 나름 오래걸렸지만 

다행히 잘 작동하는것같다 

이런건 또 자랑안하고 못배기지!

 

오늘 하루종일 이거푼다고 고생많았으니 좀 쉬어야겠다

하지만 이번에 진행중인 데이콘 대회에 나가기로 했다는점! 으악~

코랩 프로 샀으니까 야무지게 머신러닝 돌려야 돈이 안아까울것같긴하다 ㅋㅋ