[백준] 2239. 스도쿠 - 파이썬

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

 

풀이 1, 풀이 2 모두 PyPy3 기준 AC 가능(통과 가능)

 

풀이 1

Backtracking을 이용해 풀 수 있는 문제.

스도쿠를 이차원 배열에 저장하고, 0이 있는 좌표들을 리스트에 저장.

백트래킹을 이용해 모든 0이 있는 칸에 가능한 숫자를 채워준다.

recursion의 depth는 9x9 스도쿠이기 때문에 최대 81. recursion error를 걱정할 만한 깊이가 아니니 안심하고 진행.

 

처음엔 풀이 1대로 풀었다가 TLE가 나와 더 시간을 줄여야 하나? 싶어서, 풀이 2와 같이 rowCheck, colCheck 또한 boxCheck처럼 이차원 배열에 저장하는 방식으로 변경해 풀었다.

그런데 다시 보니 TLE가 나는 이유가 프로그램이 끝나지 않아서였고.. ^ㅁ^ exit() 을 넣어줌으로써 해결했다.

물론 풀이 2가 더 시간이 적게 걸리긴 하지만, 풀이 1, 풀이 2 모두 AC!

board = [list(map(int, input())) for _ in range(9)]
coors = []
'''0이 들어간 좌표 저장'''
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            coors.append((i, j))
 
 
def rowCheck(n, row):
    if n in board[row]:
        return True
    return False
 
 
def colCheck(n, col):
    for i in range(9):
        if n == board[i][col]:
            return True
    return False
 
 
'''boxCheck[n][m-1] = n번 box에 m이 포함되었는지'''
boxCheck = [[False] * 9 for _ in range(9)]
for i in range(9):
    for j in range(9):
        if board[i][j] != 0:
            boxCheck[(i//3)*3 + j//3][board[i][j]-1] = True
 
 
def backT(n):
    '''coors(0의 좌표들) 의 개수만큼 depth가 깊어졌다면, 모든 0에 숫자를 채워넣은 상태이므로, 종료.'''
    if n == len(coors):
        for b in board:
            print(*b, sep="")
        exit()
 
    '''i, j = row, column'''
    i, j = coors[n]
    for k in range(1, 10):
        if rowCheck(k, i):
            continue
        if colCheck(k, j):
            continue
        if boxCheck[(i//3)*3 + j//3][k-1]:
            continue
 
        '''row, col, box check 후 숫자 삽입'''
        board[i][j] = k
        boxCheck[(i//3)*3 + j//3][k-1] = True
 
        backT(n+1)
 
        '''만약 더 깊은 depth에서 return이 일어났다면, backTracking을 위해 원상복구.'''
        board[i][j] = 0
        boxCheck[(i//3)*3 + j//3][k-1] = False
 
backT(0)

 

 

풀이 2

board = [list(map(int, input())) for _ in range(9)]
coors = []
'''0이 들어간 좌표 저장'''
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            coors.append((i, j))
 
 
'''rowCheck[n][m-1] = n번 row에 m이 포함되었는지'''
rowCheck = [[False] * 9 for _ in range(9)]
'''colCheck[n][m-1] = n번 column에 m이 포함되었는지'''
colCheck = [[False] * 9 for _ in range(9)]
'''boxCheck[n][m-1] = n번 box에 m이 포함되었는지'''
boxCheck = [[False] * 9 for _ in range(9)]
 
for i in range(9):
    for j in range(9):
        if board[i][j] != 0:
            boxCheck[(i//3)*3 + j//3][board[i][j]-1] = True
            rowCheck[i][board[i][j]-1] = True
            colCheck[j][board[i][j]-1] = True
 
 
def backT(n):
    '''coors(0의 좌표들) 의 개수만큼 depth가 깊어졌다면, 모든 0에 숫자를 채워넣은 상태이므로, 종료.'''
    if n == len(coors):
        for b in board:
            print(*b, sep="")
        exit()
 
    '''i, j = row, column'''
    i, j = coors[n]
    for k in range(1, 10):
        if rowCheck[i][k-1]:
            continue
        if colCheck[j][k-1]:
            continue
        if boxCheck[(i//3)*3 + j//3][k-1]:
            continue
 
        '''row, col, box check 후 숫자 삽입'''
        board[i][j] = k
        boxCheck[(i//3)*3 + j//3][k-1] = True
        rowCheck[i][k-1] = True
        colCheck[j][k-1] = True
 
        backT(n+1)
 
        '''만약 더 깊은 depth에서 return이 일어났다면, backTracking을 위해 원상복구.'''
        board[i][j] = 0
        boxCheck[(i//3)*3 + j//3][k-1] = False
        rowCheck[i][k-1] = False
        colCheck[j][k-1] = False
 
backT(0)