파이썬 알고리즘 130번 | [백준 2680번] 스도쿠

Yunny.Log ·2022년 2월 26일
0

Algorithm

목록 보기
133/318
post-thumbnail

130. 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

제한
baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
C++14: 80ms
Java: 292ms
PyPy3: 1172ms
예제 입력 1 복사
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0
예제 출력 1 복사
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

1) 어떤 전략(알고리즘)으로 해결?

시도1

  • 행 하나 선택 => 그 행일 때 열검사하면 ㄱㅊ? => 열검사하면 ㄱㅊ고 3*3 검사해도 ㄱㅊ?
  • 그래서 ㄱㅊ지 않은 경우 발생하면 back
    시도2
  • 빵꾸뚫린 애들은 미리 모아놓기!!!!!!!!!!!!

2) 코딩 설명

<내 풀이>

-> 83%로 파이썬에선 시간 초과


import sys
def sdk(z,num,chk): 
    candi=[]
    chk=[0]*10

    if num==len(zero):
        for i in range(9):
            for j in range(9):
                print(arr[i][j],end=" ")
            print()
        sys.exit()
    else:
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[num][1]]]=1    #행 체크 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[num][0]][k]]=1  #열 체크
#####################################
        #3*3 검사방법 추가
        xr= (z[num][0])
        xc= (z[num][1])
        dx = (xr//3)*3
        dy = (xc//3)*3

        for i in range(dx,dx+3):
            for j in range(dy,dy+3):
                chk[arr[i][j]]=1
#######################################

        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(m)

        for i in candi:
                arr[z[num][0]][z[num][1]]=i
                sdk(z,num+1,chk)
                arr[z[num][0]][z[num][1]]=0

if __name__=="__main__":
    zero=[]
    global arr
    chk=[0]*10#1~9
    arr=[list(map(int,sys.stdin.readline().split())) for i in range(9)]
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                zero.append((i,j))#0이 행, 1이 열
    sdk(zero,0,chk)

<나의 시행착오 일대기>

  • 행 -> 열 -> 3*3 순으로 둘러볼 예정이었는데 어케 구현할 지 넘 복잡
def row(i,j,chk):
    global arr
    for k in range(10):#1~9
        chk[arr[k][j]]=1    #행 검사 - 행에서 아직 나오지 않은 숫자 collect
    for h in range(1,10):
        if chk[h]==0:#h는 후보가 되는 아이 (행에 들어갈)
            arr[i][j]=h#h를 현재 arr의 빈칸에 넣어보고 검사하기
            chk[h]=1#h체크
            if col(i,j,h):
                arr[i][j]=h
                return
            chk[h]=0
            arr[i][j]=0
            
def col(i,j,h):
    for k in range(10):
        if arr[i][k]==h:
            return False
            
    
    #모두 chk되지 않은 상황이면 또  검사해서 열 채워주기
    for h in range(1,10):#그리고 혹시 열에 안채워진애 있나 점검
        if chk[h]==0:#h는 후보가 되는 아이 (텅 빈 열에 들어갈) 



if __name__=="__main__":
    global arr
    arr=[0]*9
    chk=[0]*10
    for i in range(9):
        arr[i]=list(map(int,input().split()))
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                row(i,j,chk)#i,j는 우리가 메꿔야 할 아이의 행과 열

-> chkcol, chkrow를 나누지 말고 합쳐서가야한다!

==> 행 체크하고 열 넘기는게 아니고
행 체크 , 열 체크 하자
약간 아래 코드 느낌으로...

def row(i,j,chk):
    global arr
    for k in range(10):#1~9
        chk[arr[k][j]]=1    #행 검사 - 행에서 아직 나오지 않은 숫자 collect
    for l in range(10):
        chk[arr[i][l]]=1
    for m in range(1,10):
        if chk[m]==0:
            arr[i][j]=m

=> 위에 방향에서 빵꾸 뚫린 애들만 경우의 수 알고 싶기 때문에 그 애들을 모아주는 과정이 필요

def sdk(z):
    global arr
    for i in range(len(z)):
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[i][1]]]=1    #행 검사 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[i][0]][k]]=1  #열 검사
        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(chk[m])


if __name__=="__main__":
    candi=[]
    zero=[]
    global arr
    arr=[0]*9
    chk=[0]*10#1~9
    for i in range(9):
        arr[i]=list(map(int,input().split()))
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                #0이 행, 1이 열
                zero.append((i,j))
    sdk(zero)

=> 위와 같이 진행 : 빵꾸뚫린 애에 들어갈 수 있는 애 (chk에 1되지 않은 애) 선별해두었음

def sdk(z,num):
    global arr
    if num==len(z):
        return True
    else :
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[num][1]]]=1    #행 검사 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[num][0]][k]]=1  #열 검사
        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(chk[m])
        if len(candi)==0:
            return False
        else :
            for i in candi:
                arr[z[num][0]][z[num][1]]=i
                chk=[]
                sdk(z,num+1)
                arr[z[num][0]][z[num][1]]=0

if __name__=="__main__":
    candi=[]
    zero=[]
    arr=[0]*9

    for i in range(9):
        arr[i]=list(map(int,input().split()))
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                #0이 행, 1이 열
                zero.append((i,j))
    chk=[0]*10#1~9
    sdk(zero,0)#zero의 0번째 인덱스부터 검사하긔
    print("________________________")
    for i in range(9):
        for j in range(9):
            print(arr[i][j], end=" ")
        print()

=> num이 zero(빵꾸난애들 모아둔 리스트) 길이랑 the same해지면 stop하도록
=> 근데 return 했는데 조건에 부합했는데도 스탑하지 않는다..why..??(아래 코드)

def sdk(z,num,chk):
    global arr
    print(num)
    print(len(z))
    if num==len(z):
        print("stop")
        return arr
    else:
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[num][1]]]=1    #행 검사 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[num][0]][k]]=1  #열 검사
        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(chk[m])
        if len(candi)==0:
            return False
        else :
            for i in candi:
                arr[z[num][0]][z[num][1]]=i
                chk=[0]*10
                chk[i]=1
                sdk(z,num+1,chk)
                arr[z[num][0]][z[num][1]]=0

if __name__=="__main__":
    candi=[]
    zero=[]
    global arr
    arr=[0]*9
    chk=[0]*10#1~9
    for i in range(9):
        arr[i]=list(map(int,input().split()))
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                zero.append((i,j))#0이 행, 1이 열
    full=sdk(zero,0,chk)
    for i in range(9):
        for j in range(9):
            print(full[i][j])
  • 문제의 결과 화면은 아래와 같음
  • stop하라는 아우성을 print.....
  • 아무래도 안에서 계속 재귀가 되기 때문이게쮜..?
  • 계속 반복되는 건 요놈..

    return 썼는 데도 계속 반복됐던 원인 ..
    내가 full=sdk로 해놓고 쟤를 계속 print하게 해서..^^

원인

    full=sdk(zero,0,chk)
    for i in range(9):
        for j in range(9):
            print(full[i][j])

나름 수정+보완을 했는데 재귀가 끝나도 arr이 전혀 번하지가 않는드앙

def sdk(z,num,chk):
    candi=[]
    if num==len(z):
        return arr
    else:
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[num][1]]]=1    #행 검사 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[num][0]][k]]=1  #열 검사
        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(m)
        if len(candi)==0:
            return False
        else :
            for i in candi:
                arr[z[num][0]][z[num][1]]=i
                chk=[0]*10
                chk[i]=1
                sdk(z,num+1,chk)
                arr[z[num][0]][z[num][1]]=0
                chk=[0]*10

if __name__=="__main__":

    zero=[]
    global arr
    arr=[0]*9
    chk=[0]*10#1~9
    for i in range(9):
        arr[i]=list(map(int,input().split()))
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                zero.append((i,j))#0이 행, 1이 열
    sdk(zero,0,chk)
    print("_______________________________________")
    for i in range(9):
        for j in range(9):
            print(arr[i][j],end=" ")
        print()


=> 출력해서 살펴보니

요만큼까지만 진행된당 호엥~~~밑에 빵꾸들은 안채워짐

  • 나는 num이 len(zero)일 때, 즉 빵꾸들의 갯수만큼 다다르면 멈추게 했는데 자꾸 num 0,1,2까지만 하고 멈춰버린다.. why????

why

=> 왜냐하면 내가 재귀를 candi가 존재할 때로 한정해놨거등...^^
=> candi가 0이 되면 더 이상 재귀 안돌아..ㅎㅎ;;;

  • 그래도 계속 제대로 된 결과가 나오지 않아서 전부 다 보이게 해놨는데 chk가 모두 1로 돼있어서 candi가 적절히 갱신이 되지 않음.. chk를 그래서 매번 초기화해주기 추가함

--> 그렇다 답은 chk가 적절히 초기화되지 않고 있었다는 것..흑흑

  • sdk가 호출될 때마다 chk가 초기화되게 설정해주니 아주...아주..잘된다
def sdk(z,num,chk): 
    candi=[]
    chk=[0]*10
    if num==len(zero):
        print("--------------------------------")
        for i in range(9):
            for j in range(9):
                print(arr[i][j],end=" ")
            print()
        print("--------------------------------")
        return
    else:
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[num][1]]]=1    #행 검사 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[num][0]][k]]=1  #열 검사
        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(m)
        if len(candi):
            for i in candi:
                arr[z[num][0]][z[num][1]]=i
                sdk(z,num+1,chk)
                arr[z[num][0]][z[num][1]]=0
        else :
            sdk(z,num+1,chk)

if __name__=="__main__":
    zero=[]
    global arr
    arr=[0]*9
    chk=[0]*10#1~9
    for i in range(9):
        arr[i]=list(map(int,input().split()))
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                zero.append((i,j))#0이 행, 1이 열
    sdk(zero,0,chk)

-> 결과

네~~~하지만 당당히 시간초과

def sdk(z,num,chk): 
    candi=[]
    chk=[0]*10
    if num==len(zero):
        for i in range(9):
            for j in range(9):
                print(arr[i][j],end=" ")
            print()
            exit
    else:
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[num][1]]]=1    #행 검사 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[num][0]][k]]=1  #열 검사
        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(m)
        if len(candi):
            for i in candi:
                arr[z[num][0]][z[num][1]]=i
                sdk(z,num+1,chk)
                arr[z[num][0]][z[num][1]]=0
        else :
            sdk(z,num+1,chk)

if __name__=="__main__":
    zero=[]
    global arr
    arr=[0]*9
    chk=[0]*10#1~9
    for i in range(9):
        arr[i]=list(map(int,input().split()))
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                zero.append((i,j))#0이 행, 1이 열
    sdk(zero,0,chk)
  • 개선 작업 need
import sys
def sdk(z,num,chk): 
    candi=[]
    chk=[0]*10

    if num==len(zero):
        for i in range(9):
            for j in range(9):
                print(arr[i][j],end=" ")
            print()
        sys.exit()
    else:
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[num][1]]]=1    #행 체크 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[num][0]][k]]=1  #열 체크
        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(m)
        if len(candi):
            for i in candi:
                arr[z[num][0]][z[num][1]]=i
                sdk(z,num+1,chk)
                arr[z[num][0]][z[num][1]]=0
        else :
            sdk(z,num+1,chk)

if __name__=="__main__":
    zero=[]
    global arr
    chk=[0]*10#1~9
    arr=[list(map(int,sys.stdin.readline().split())) for i in range(9)]
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                zero.append((i,j))#0이 행, 1이 열
    sdk(zero,0,chk)
  • sys로 읽는 것으로 수정

틀렸습니당 (3*3 박스 검사 안함;)

=> 근데 1%만에 틀림...........흑흑 why....?
=> row랑 column만 검사하고 내 주변 8개 검사는 안했기 때문이라고 추정
https://hwiyong.tistory.com/305 이 분의 3*3검사 방법을 참조해 추가하겠습니당

        x = zeros[index][0]
        y = zeros[index][1]
        dx = (x//3) * 3
        dy = (y//3) * 3
        ________________________________________
        # 3*3 box 검사
        for i in range(dx, dx + 3):
            for j in range(dy, dy + 3):
                check_num = sdk[i][j]
                if(check_num):
                    num_list[check_num] = False
  • 추가했는데도 틀렸다고 뜬다...흐앙 어디가 틀린 건지 따져봐야지 흑흑
import sys
def sdk(z,num,chk): 
    candi=[]
    chk=[0]*10

    if num==len(zero):
        for i in range(9):
            for j in range(9):
                print(arr[i][j],end=" ")
            print()
        sys.exit()
    else:
        for k in range(9):#arr은 0~8 (9개)
            chk[arr[k][z[num][1]]]=1    #행 체크 - 행에서 아직 나오지 않은 숫자 collect
            chk[arr[z[num][0]][k]]=1  #열 체크
#####################################
        #3*3 검사방법 추가
        xr= (z[num][0])
        xc= (z[num][1])
        dx = (xr//3)*3
        dy = (xc//3)*3

        for i in range(dx,dx+3):
            for j in range(dy,dy+3):
                chk[arr[i][j]]=1
#######################################

        for m in range(1,10):
            if chk[m]==0: # 빈 칸에 들어갈 값 후보들
                candi.append(m)

        if len(candi):
            for i in candi:
                arr[z[num][0]][z[num][1]]=i
                sdk(z,num+1,chk)
                arr[z[num][0]][z[num][1]]=0
        else :
            sdk(z,num+1,chk)

if __name__=="__main__":
    zero=[]
    global arr
    chk=[0]*10#1~9
    arr=[list(map(int,sys.stdin.readline().split())) for i in range(9)]
    for i in range(9):
        for j in range(9):
            if arr[i][j]==0:
                zero.append((i,j))#0이 행, 1이 열
    sdk(zero,0,chk)

<반성 점>

  • 스도쿠를 마지막으로 아주 백트랙킹에 대해 잘 탐색하고 이해할 수 있는 시간이었다.

<배운 점>

  • 정지 조건을 잘 설정해주어야 한다는 것을 명심하고 초기화 될 것, global로 선언해줄 것 잘 구별해서 자리잡게 해주자
  • 이차원 배열 입력 및 탐색 방법 with sys
sdk = [list(map(int, input().split())) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if sdk[i][j] == 0]
  • 3*3 찾기
def checkRect(x, y, a):
    nx = x // 3 * 3
    ny = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if a == graph[nx+i][ny+j]:
                return False
    return True
profile
Yunny.Log
이전 포스트

파이썬 알고리즘 129번 | [백준 9663번] N-Queen

다음 포스트

파이썬 알고리즘 131번 | [백준 14889번] 스타트와 링크-예외 찾아내기

0개의 댓글