파이썬 알고리즘 233번 | [백준 2580번] 스도쿠 - 재도전 중

Yunny.Log ·2022년 8월 11일

Algorithm

목록 보기

237/318

~~텍스트~~### 233. 스도쿠

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

2) 코딩 설명

<내 풀이>

< 내 틀렸던 풀이, 문제점>

최초

import sys
from collections import deque
# dfs bfs
sudo = []
for i in range(9) : 
    sudo.append(list(map(int, sys.stdin.readline().rstrip().split())))

# 빈칸은 0 
blank = deque()
for r in range(9) :
    for c in range(9) : 
        if sudo[r][c]==0 : 
            blank.append((r,c))

while blank : 
    nowr, nowc = blank.pop()
    #print("nowr , nowc ", nowr, nowc)
    chk = [0 for _ in range(10)]

    # 행 / 열 / 내 주위 9 개
    for ridx in range(9) : 
        chk[sudo[nowr][ridx]] = 1

    for cidx in range(9) : 
        chk[sudo[cidx][nowc]] = 1

    for idx in range(nowr//3*3, nowr//3*3+3) : 
        for jdx in range(nowc//3*3, nowc//3*3+3) : 
            #print(idx,jdx)
            chk[sudo[idx][jdx]] = 1

    #print(chk)

    for c in range(1,10) : #1,9
        if chk[c]==0 :
            sudo[nowr][nowc] = c

for ss in sudo : 
    for s in ss : 
        print(s,end=" ")
    print()

최초에다가 재귀를 곁들임

import sys
from collections import deque
sudo = []
for i in range(9) : 
    sudo.append(list(map(int, sys.stdin.readline().rstrip().split())))

# 빈칸은 0 
def sudok(sudo) : 
    blank = deque()
    for r in range(9) :
        for c in range(9) : 
            if sudo[r][c]==0 : 
                blank.append((r,c))
    
    if len(blank)==0 : 
        for ss in sudo : 
            for s in ss : 
                print(s,end=" ")
            print()
        return

    while blank : 
        nowr, nowc = blank.popleft()
        print("nowr , nowc ", nowr, nowc)
        # for ss in sudo : 
        #     for s in ss : 
        #         print(s,end=" ")
        #     print()
        chk = [0 for _ in range(10)]

        # 행 / 열 / 내 주위 9 개
        for ridx in range(9) : 
            #print(sudo[nowr][ridx], end=" ")
            chk[sudo[nowr][ridx]] = 1

        for cidx in range(9) : 
            #print(sudo[cidx][nowc], end=" ")
            chk[sudo[cidx][nowc]] = 1

        for idx in range(nowr//3*3, nowr//3*3+3) : 
            for jdx in range(nowc//3*3, nowc//3*3+3) : 
                #print(idx,jdx)
                chk[sudo[idx][jdx]] = 1
        print(chk)

        if sum(chk)==9 : 
            return

        for c in range(1,10) : #1,9
            if chk[c]==0 :
                sudo[nowr][nowc] = c
                sudok(sudo)
                for ss in sudo : 
                    for s in ss : 
                        print(s,end=" ")
                    print()
                print()
                sudo[nowr][nowc] = 0

sudok(sudo)

미스터리 부분

now 2 8 | [1, 1, 1, 1, 1, 1, 0, 1, 1, 1] 6 0 yay
1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 0 0 0
7 8 9 0 0 0 4 2 6
2 1 4 3 6 5 8 9 7
3 6 5 9 7 8 2 1 4
9 7 8 2 1 4 6 3 5
5 3 1 6 4 2 9 7 8
8 4 7 5 9 1 3 6 2
6 9 2 8 3 7 5 4 1
now 2 1 | [1, 1, 1, 1, 1, 1, 1, 1, 0, 0] 9 0 yay
1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 0 0 0
7 9 9 0 0 0 4 2 6
2 1 4 3 6 5 8 9 7
3 6 5 9 7 8 2 1 4
9 7 8 2 1 4 6 3 5
5 3 1 6 4 2 9 7 8
8 4 7 5 9 1 3 6 2
6 9 2 8 3 7 5 4 1

        for idx in range(nowr//3*3, nowr//3*3+3) : 
            for jdx in range(nowc//3*3, nowc//3*3+3) : 
                print(nowr, nowc , "+++++++++", idx, jdx)
                chk[sudo[idx][jdx]] = 1

내 주변 아홉개 조사하는 것에서 크리티컬한 로지컬 에러가 발생했던 것이지. (반성점에 자세..)

으앙 그래도 안된다 ㅠㅠ 반례가 안되네네에에

import sys
from collections import deque
sudo = []
for i in range(9) : 
    sudo.append(list(map(int, sys.stdin.readline().rstrip().split())))

visit = list([0 for _ in range(9)] for _ in range(9))
total = []
# 동서남북 & 대각선 네 개
x = [-1,1,0,0,-1,-1,1,1] 
y = [0,0,-1,1,-1,1,-1,1]

def sudok(sudokk) : 
    global total
    blank = deque()
    for r in range(9) :
        for c in range(9) : 
            if sudokk[r][c]==0 : # 빈칸 0 
                blank.append((r,c))
                
    while blank : 
        nowr, nowc = blank.popleft()
        chk = [0 for _ in range(10)]

        # 행 / 열 / 내 주위 9 개
        for ridx in range(9) : 
            chk[sudokk[nowr][ridx]] = 1 
            chk[sudokk[ridx][nowc]] = 1
            
        for idx in range(8) : 
            tmpr, tmpc = nowr+x[idx], nowc+y[idx]
            if 0<=tmpr<9 and 0<=tmpc<9 :
                chk[sudokk[tmpr][tmpc]] = 1

        if (nowr==0 and nowc==0) or (nowr==0 and nowc==0) :
            print(nowr, nowc)
            print(chk)

        if len(blank)==0 : 
            total.append(sudo)

        for c in range(1,10) : #1~9
            if chk[c]==0 :
                sudokk[nowr][nowc] = c
                sudok(sudokk)

        # if len(blank)==0 : 
        #     total.append(sudo)
        # print()
sudok(sudo)

for tt in total[-1]:
    print(" ".join(map(str,tt)))

왜 안될까 뭐가 문젤까 코드

import sys
from collections import deque
sudo = []
for i in range(9) : 
    sudo.append(list(map(int, sys.stdin.readline().rstrip().split())))

visit = list([0 for _ in range(9)] for _ in range(9))
total = []
# 동서남북 & 대각선 네 개
x = [-1,-1,1,1] 
y = [-1,1,-1,1]

def sudok(sudokk) : 
    global total
    blank = deque()
    for r in range(9) :
        for c in range(9) : 
            if sudokk[r][c]==0 : # 빈칸 0 
                blank.append((r,c))
                    
    # if len(blank)==0 : 
    #         total.append(sudo)   

    while blank : 
        nowr, nowc = blank.popleft()
        chk = [0 for _ in range(10)]
        # print("now ", nowr,nowc, sudokk[nowr][nowc])
        # 행 / 열 / 내 주위 9 개
        for ridx in range(9) : 
            # print(nowr, ridx, sudokk[nowr][ridx])
            # print(ridx, nowc, sudokk[ridx][nowc])
            chk[sudokk[nowr][ridx]] = 1 
            chk[sudokk[ridx][nowc]] = 1
            
        for idx in range(4) : 
            tmpr, tmpc = nowr+x[idx], nowc+y[idx]
            if 0<=tmpr<9 and 0<=tmpc<9 :
                chk[sudokk[tmpr][tmpc]] = 1

        if len(blank)==0 : 
            total.append(sudo)   
        # print('\n', nowr, nowc, "nowwwwwwwwwwwwwwww")
        # for ch in range(10) :
        #     print(chk[ch], end=" ")
        if sum(chk[1:10])==9 : 
            return
        for c in range(1,10) : #1~9
            if chk[c]==0 :
                sudokk[nowr][nowc] = c
                sudok(sudokk)
                sudokk[nowr][nowc] = 0 
            #print()



sudok(sudo)
print()
for tt in total[-1]:
    print(" ".join(map(str,tt)))

반례

https://www.acmicpc.net/board/view/87922
0 0 0 0 0 0 0 0 9
0 0 0 0 0 0 0 0 8
0 0 0 0 0 0 0 0 7
0 0 0 0 0 0 0 0 6
0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 1

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

나의 5개월 전 풀이

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)

<반성 점>

정말 나를 왜그렇게 믿었던 것일까 ㅎㅎ 끊임없이 나를 의심해야 한다

기존 내 주변 감싸는 8개 탐색 로직

        for idx in range(nowr//3*3, nowr//3*3+3) : 
            for jdx in range(nowc//3*3, nowc//3*3+3) : 
                print(nowr, nowc , "+++++++++", idx, jdx)
                chk[sudo[idx][jdx]] = 1

위 로직의 크리티컬 예외

바꾼 후

x = [-1,1,0,0,-1,-1,1,1] 
y = [0,0,-1,1,-1,1,-1,1]

        for idx in range(8) : 
            tmpr, tmpc = nowr+x[idx], nowc+y[idx]
            if 0<=tmpr<9 and 0<=tmpc<9 :
                chk[sudo[tmpr][tmpc]] = 1