[Python] 백준 2239번 스도쿠

2239번: 스도쿠

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

코드

sudoku = [list(map(int,input())) for _ in range(9)]
# 빈칸 저장
emp = []
for i in range(9):
    for j in range(9):
        if sudoku[i][j] == 0:
            emp.append((i, j))

# 3X3 사각형 체크
def chk_3X3(x, y, num):
    r = (x // 3) * 3
    c = (y // 3) * 3
    for i in range(3):
        for j in range(3):
            if sudoku[r+i][c+j] == num: # 겹치는 번호 있으면 return False
                return False
    return True

# 가로줄 체크
def chk_row(x, y, num):
    for i in range(9):
        if sudoku[x][i] == num:
            return False
    return True

# 세로줄 체크
def chk_col(x, y, num):
    for i in range(9):
        if sudoku[i][y] == num:
            return False
    return True

def dfs(cnt):
    if cnt == len(emp):
        for i in range(9):
            for j in range(9):
                print(sudoku[i][j], end="")
            print()
        exit() 
        
    r, c = emp[cnt]
    for k in range(1, 10):
        if chk_3X3(r, c, k) and chk_col(r, c, k) and chk_row(r, c, k):
            sudoku[r][c] = k
            dfs(cnt + 1)
            sudoku[r][c] = 0       
              
dfs(0)

1. 입력받은 스도쿠에서 빈칸들의 위치를 emp라는 배열에 튜플 형태로 저장해둔다.
2. 이제 dfs를 이용하여 스도쿠의 빈 칸들을 채워본다. dfs로 재귀의 깊이가 emp 배열의 길이와 같아질 때까지 재귀적으로 구현했다.
   1. 빈 칸을 하나씩 확인하며 숫자를 1 ~ 9까지 대입해본다. 
   2. 숫자가 들어갈 수 있다면 cnt를 하나 증가시켜준 값을 인자로 넘겨주며 dfs를 호출한다. 어떠한 숫자도 들어갈 수 없다면 다시 0으로 초기화시켜주고 되돌아간다. 그러면 이전 빈 칸으로 돌아가 다음 숫자를 넣어보게 될 것이다. (백 트래킹)
   3. 재귀의 깊이가 emp 배열의 깊이와 같아졌다면 빈 칸들을 모두 채워준 것이므로 완성된 배열을 출력하고 프로그램을 종료한다.

 

PyPy3로는 되는데 파이썬으로는 시간 초과가 난다....