백준 2293 : 스도쿠 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Number(i,j):
    if 0<=i<3 and 0<=j<3:
        return 0
    if 0<=i<3 and 3<=j<6:
        return 1
    if 0<=i<3 and 6<=j<9:
        return 2
    if 3<=i<6 and 0<=j<3:
        return 3
    if 3<=i<6 and 3<=j<6:
        return 4
    if 3<=i<6 and 6<=j<9:
        return 5
    if 6<=i<9 and 0<=j<3:
        return 6
    if 6<=i<9 and 3<=j<6:
        return 7
    else:
        return 8

def BackTracking(graph,total  , Breath , High , Box):

    if total==0: # 종료조건.
        for i in graph:
            Answer=''.join(i)
            print(Answer)
        exit(0)
    tmp=0


    for i in range(9):
        for j in range(9):
            if graph[i][j]=="0":
                tmp+=1
                if tmp==1:
                    for value in range(1,10):
                        NUMBER=Number(i,j)
                        if (i,value) not in Breath and (j,value) not in High and (NUMBER,value) not in Box:

                            graph[i][j]=str(value)

                            Breath.add((i,value))
                            High.add((j,value))
                            Box.add((NUMBER,value))

                            BackTracking(graph,total-1 , Breath , High , Box)

                            graph[i][j]="0"
                            Breath.remove((i,value))
                            High.remove((j,value))
                            Box.remove((NUMBER,value))


graph=[ list(map(str,input().rstrip())) for i in range(9) ]
total = 0

Breath=set() ; High=set() ; Box=set()

for i in range(9):
    for j in range(9):
        if graph[i][j]=="0":
            total+=1
        else:
            Breath.add((i,int(graph[i][j])))
            High.add((j,int(graph[i][j])))
            Box.add((Number(i,j) , int(graph[i][j])))


BackTracking(graph,total , Breath , High , Box)

📌 어떻게 접근할 것인가?

백트래킹을 사용해 풀었습니다.

set 을 사용해서 가로 , 세로 , 3 × 3 사각형에 대해 값이 존재하지 않는지 체크후에
모두 다 값이 존재하지 않다면 작은 숫자부터 넣어줍니다.

이후 재귀가 끝나면 원레 graph 값을 0 으로 되돌려놓고 set 의 원소를 삭제 해줍니다.

또한 처음 그래프를 입력받을때도 set 에 0 이 아닌 값에 대해서 좌표와 값을 set 에 넣었습니다.

총 3개의 set - $Breath$ , $High$ , $Box$ 를 사용했습니다.

if (i,value) not in Breath and (j,value) not in High and (NUMBER,value) not in Box:

위와같이 세로줄 , 가로줄 , 작은사각형안에 value 값이 없는지 체크해주었습니다.

def Number(i,j): 함수를 통해 현재 x,y 좌표값에 따라서 사각형의 위치를 0~8까지 반환하는 식으로 구성했습니다.