[백준] 2580번 스도쿠 - python파이썬 (백트래킹)

문제

 

 

 

 

 

이 문제에서 고려해야하는 것은 크게 2가지이다

 

1. 가로, 세로에 1~9까지의 숫자가 한번만 나타나야 한다.
2. 굵은 선으로 구분된 정사각형안에 1~9가 한번만 나타나야한다.

 

 

 

이 조건을 해결하기 위해 함수를 따로 만들어 주었다.

 

그리고 이 문제는 완전탐색을 해주어야하는데 최대한 효율적으로 확인하기 위해 백트래킹 기법을 사용해주었다.

 

 

 

전체코드

 

sdoku = [list(map(int,input().split())) for _ in range(9)]

#x행을 확인하는 함수
def row(x,a):
    for i in range(9):
        if a == sdoku[x][i]:
            return False
    return True

#y열을 확인하는 함수
def col(y,a):
    for i in range(9):
        if a == sdoku[i][y]:
            return False
    return True

#x, y가 속한 정사각형을 확인하는 함수
def square(x,y,a):
    for i in range(3):
        for j in range(3):
            if a == sdoku[x//3*3 + i][y//3*3 + j]:
                return False
    return True

def backtracking(n):
    #빈칸을 모두 채웠다면 종료
    if n == len(blank):
        for s in sdoku:
            print(*s)
        exit(0)
    
    #1~9의 숫자 전부 확인
    for i in range(1,10):
        x = blank[n][0]
        y = blank[n][1]
        #i가 가로, 세로, 정사각형안에도 없다면
        if row(x,i) and col(y,i) and square(x,y,i):
            sdoku[x][y] = i
            backtracking(n+1)
            #다른 경우의 수를 확인하기 위해 복구
            sdoku[x][y] = 0 


blank = []
for i in range(9):
    for j in range(9):
        if sdoku[i][j] == 0:
            blank.append([i,j])
backtracking(0)

 

 

 

조건에 따라서 함수를 작성하여 이를 활용하는 방법을 생각하는 것이 가장 중요했던 문제였던 것 같다.